无限排序数组中二进制搜索的索引错误

Question

程序在二分查找中给出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)
# This is a function that searches elements in an infinite sorted array
# l=array;ele=element
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)

Answer 1

high 的值在每个循环中加倍，当 high 的值大于或等于列表的长度时，它给出 IndexError: list index out of range

def binarySearchInfiniteSortedArray(l,ele):
    low,high=0,1
    while(True):
        try:
            pEle = l[high]
        except:
            high = int((high**0.5)*(low**0.5))
            continue
        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)

一旦出现错误，我们就可以尝试 except 并得到 high 和 low 的几何平均值，除非您再次在范围内或得到答案。希望我的观点很清楚。

无限排序数组中二进制搜索的索引错误

Index error in binary search in an infinite sorted array

python

arrays

algorithm

binary-search

index-error