Follow

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use
Contact

Index error in binary search in an infinite sorted array

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)

>Solution :

MEDevel.com: Open-source for Healthcare and Education

Collecting and validating open-source software for healthcare, education, enterprise, development, medical imaging, medical records, and digital pathology.

Visit Medevel

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.

Add a comment

Leave a Reply

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use

Discover more from Dev solutions

Subscribe now to keep reading and get access to the full archive.

Continue reading