Find the smallest number that is greater than a gi…

Given a sorted list of numbers, I need to find the smallest number that is greater than a given number. Consider this list:

arr=[1,2,3,5,7,11,101,131,151,181,191,313,353,373,383]

Say the specified number is 320. Then, my method should return 353 as 353 is the smallest number greater than 320.

I am trying to use a slightly modified form of binary search; however on execution the program goes into infinite loop.

def modBinarySearch(arr,x):
    l=len(arr)
    mid=l/2
    if arr[mid]>=x and arr[mid-1]<x:
        return arr[mid]
    elif arr[mid]>x and arr[mid-1]>x:
        modBinarySearch(arr[mid:l],x)
    else: 
        modBinarySearch(arr[0:mid],x)

N=int(raw_input())
arr=[1,2,3,5,7,11,101,131,151,181,191,313,353,373,383]
print modBinarySearch(arr,N)

Can someone point out what I am doing wrong ?

Answer

If arr[mid] and arr[mid-1], both are greater than your number, you should search in arr[0:mid], don’t you think?

 elif arr[mid]>x and arr[mid-1]>x:
    modBinarySearch(arr[0:mid],x)
else: 
    modBinarySearch(arr[mid:1],x)

Find the smallest number that is greater than a given number in a sorted list

Advertisement

Answer