无限有序数组二分查找触发IndexError列表索引越界错误问题

对无限有序数组执行*二分查找（binary search）*时，若待查找元素不存在或数值大于数组所有元素，原有实现会抛出IndexError: list index out of range错误。

原错误实现代码 #

def binarySearch(l,ele,low=0,high=None):
    if(high==None):
        high=len(l)-1
    if(low>high):
        return -1
    mid= int((low+high)/2)
    pEle = l[mid]
    if(pEle==ele):
            return mid 
    elif(pEle>ele):
        return binarySearch(l,ele,low,mid-1)
    else:
        return binarySearch(l,ele,mid+1,high)

# 无限有序数组元素查找函数
# 入参：l为有序数组，ele为待查找目标元素
def binarySearchInfiniteSortedArray(l,ele):
    low,high=0,1
    while(True):
        pEle = l[high]
        if(pEle==ele):
            return high
        elif(pEle>ele or pEle==l[-1]):
            break
        else:
            low,high = high+1,high*2
    return binarySearch(l,ele,low,high)

错误根源 #

• 实现逻辑没有提前校验high的取值是否超过数组的最大索引，直接访问l[high]获取元素。当目标元素大于数组中所有元素时，high会按照每次翻倍的规则持续增大，最终超过数组的最大索引值，触发索引越界报错。
• 原代码中的pEle==l[-1]判断逻辑只有当high刚好等于数组最大索引时才会生效，一旦high超过该值，程序还没走到这个判断就会因为访问越界提前报错。

修复方案 #

访问l[high]前先判断high是否超出数组最大索引，若超出则直接将上界设为数组最大索引，再进入普通二分查找逻辑即可，修复后代码如下：

def binarySearchInfiniteSortedArray(l,ele):
    low,high=0,1
    max_idx = len(l) - 1
    while True:
        # 提前判断high是否越界，避免取值报错
        if high > max_idx:
            high = max_idx
            break
        pEle = l[high]
        if pEle == ele:
            return high
        elif pEle > ele:
            break
        else:
            low, high = high + 1, high * 2
    return binarySearch(l, ele, low, high)

内容的提问来源于stack exchange，提问作者Ankit Kumar Jha