educative.io

Educative

More ad hoc solution

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

1 Like

HI @Andres_Parra

Your solution seems fine.

Happy learning :slight_smile:

1 Like