It bugs me that the proposed solution can find the target while looking for the max, but doesn’t stop right there. Here is my proposal, any comments?
def search_bitonic_array_mine(arr, key):
start = 0
end = len(arr) - 1
ascending_result = None
descending_result = None
while start <= end:
mid = start + (end - start) // 2
if arr[mid] == key:
return mid
if mid + 1 > end:
break
if arr[mid] < arr[mid + 1]:
if arr[mid] > key:
if not ascending_result:
ascending_result = agnostic_search(arr, key, start, mid - 1)
if ascending_result != -1:
return ascending_result
start = mid + 1
else:
start = mid + 1
else:
if arr[mid] > key:
if not descending_result:
descending_result = agnostic_search(arr, key, mid + 1, end)
if descending_result != -1:
return descending_result
end = mid - 1
else:
end = mid - 1
return -1
def agnostic_search(arr, key, start, end):
desc = arr[start] > arr[end]
while start <= end:
mid = start + (end - start) // 2
if arr[mid] == key:
return mid
elif arr[mid] > key and desc or arr[mid] < key and not desc:
end = mid - 1
else:
start = mid + 1
return -1
Type your question above this line.
Course: https://www.educative.io/collection/5668639101419520/5671464854355968
Lesson: https://www.educative.io/collection/page/5668639101419520/5671464854355968/5585107094077440