Index error in binary search in an infinite sorted array

Question

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)

You may try with arithematic mean to get into the range however the geometric mean will get you to the answer faster. — Rahul Kumar Jha
– Rahul Kumar Jha, Commented Nov 18, 2021 at 7:17

Rahul Kumar Jha · Accepted Answer · 2021-11-16 05:50:06Z

1

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.

answered Nov 16, 2021 at 5:50

Rahul Kumar Jha

3691 silver badge10 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Index error in binary search in an infinite sorted array

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related