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 ?
Advertisement
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)