The program gives IndexError: list index out of range in binary search in the infinite sorted array when the element does not exist or is too large

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)

CodePudding user response：

value of high is getting doubled in each loop and when the value of high becomes greater than or equal to the length of list it gives 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)

Once the error is there we can do a try except and get the Geometrical mean of high and low unless u are inside the range again or get the answer. Hope my points are clear.