The task is to find "crossover" index of two arrays. The crossover index is the index, that for array x and y: assert(x[left] > y[left]) assert(x[right] < y[right])
I am supposed to use recursion to solve this problem. Test case to pass are:
Test 1: x, y = [0, 1, 2, 3, 4, 5, 6, 7], [-2, 0, 4, 5, 6, 7, 8, 9]
Test 2: x, y = [0, 1, 2, 3, 4, 5, 6, 7], [-2, 0, 4, 4.2, 4.3, 4.5, 8, 9]
Test 3: x, y = [0, 1], [-10, 10]
Test 4: x, y = [0, 1, 2, 3], [-10, -9, -8, 5]
I modified the binary search algorithm. Below is my code:
def findCrossoverIndexHelper(arr_x, arr_y, left, right):
if len(x) == len(y) and 0 <= left <= right - 1 and right < len(x):
mid = (left + right) // 2
if arr_x[mid] >= arr_y[mid] and arr_x[mid + 1] < arr_y[mid + 1]:
print("This executes")
return mid
elif arr_x[mid] < arr_y[mid] and arr_x[mid + 1] > arr_y[mid + 1]:
print("This executes 1")
return findCrossoverIndexHelper(arr_x, arr_y, mid + 1, right)
else:
print("This executes 2")
return findCrossoverIndexHelper(arr_x, arr_y, left, mid - 1)
My code passes Test cases 1, 2 and 3, but it can't pass 4.
Do you have any suggestions where I am wrong or what I miss?
Thank you!
The following function should work:
def findCrossoverIndexHelper(arr_x, arr_y, left, right):
if len(x) == len(y) and 0 <= left <= right - 1 and right < len(x):
mid = (left + right) // 2
if arr_x[mid] >= arr_y[mid] and arr_x[mid + 1] < arr_y[mid + 1]:
return mid
elif arr_x[mid] < arr_y[mid] and arr_x[mid + 1] > arr_y[mid + 1]:
return findCrossoverIndexHelper(arr_x, arr_y, mid + 1, right)
elif arr_x[mid] > arr_y[mid] and arr_x[mid + 1] > arr_y[mid + 1]:
return findCrossoverIndexHelper(arr_x, arr_y, mid + 1, right)
else:
return findCrossoverIndexHelper(arr_x, arr_y, left, mid - 1)