Giả sử chúng ta có một dãy bitonic, chúng ta phải tìm Điểm Bitonic trong đó. Như chúng ta biết, Dãy Bitonic là một dãy số tăng chặt sau đó sau một điểm nhất định nó giảm chặt. Điểm này gọi là điểm bitonic. Đối với dãy chỉ tăng hoặc chỉ giảm, không có điểm bitonic.
Ví dụ, nếu đầu vào là [7, 8, 9, 12, 10, 6, 3, 2], thì đầu ra sẽ là 12.
Để giải quyết, chúng ta làm theo các bước:
- Định nghĩa hàm binary_search(array, l, r)
- Nếu l <= r, thì m := (l + r) // 2
- Nếu array[m-1] < array[m] và array[m] > array[m+1], trả về m
- Nếu array[m] < array[m+1], trả về binary_search(array, m+1, r)
- Ngược lại, trả về binary_search(array, l, m-1)
- Trả về -1
Ví dụ
def binary_search(array, l, r):
if (l <= r):
m = (l + r) // 2
if (array[m - 1] < array[m] and array[m] > array[m + 1]):
return m
if (array[m] < array[m + 1]):
return binary_search(array, m + 1, r)
else:
return binary_search(array, l, m - 1)
return -1
array = [7, 8, 9, 12, 10, 6, 3, 2]
n = len(array)
index = binary_search(array, 1, n-2)
if (index != -1):
print(array[index])
Đầu vào
[7, 8, 9, 12, 10, 6, 3, 2]
Đầu ra
12