在Python中使用修改后的二分搜索算法查找“交叉”索引

Question

任务是找到两个数组的“交叉”索引。交叉索引是数组 x 和 y 的索引： 断言(x[左] > y[左]) 断言(x[右] < y[right])

我应该使用递归来解决这个问题。 要通过的测试用例是：

测试1： x, y = [0, 1, 2, 3, 4, 5, 6, 7], [-2, 0, 4, 5, 6, 7, 8, 9]

测试2： x, y = [0, 1, 2, 3, 4, 5, 6, 7], [-2, 0, 4, 4.2, 4.3, 4.5, 8, 9]

测试3： x, y = [0, 1], [-10, 10]

测试4： x, y = [0, 1, 2, 3], [-10, -9, -8, 5]

我修改了二分查找算法。下面是我的代码：

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)

我的代码通过了测试用例 1、2 和 3，但无法通过 4。

您对我错误或遗漏的地方有什么建议吗？

谢谢！

Answer 1

以下功能应该可以工作：

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)

Answer 2

对我来说这段代码有效

def findCrossoverIndexHelper(x, y, left, right):
    if len(x) == len(y) and 0 <= left <= right - 1:
        mid = (left + right) // 2
        if x[mid] >= y[mid] and x[mid+1] < y[mid+1]:
            return mid
        elif (x[mid] > y[mid] or x[mid] < y[mid]) and x[mid+1] > y[mid+1]:
            return findCrossoverIndexHelper(x,y,mid+1,right) 
        else:
            return findCrossoverIndexHelper(x,y,left,mid-1)