CODEWITHSUNDEEP
pythonalgorithmbinary-search
OneMoreError
OneMoreError

Reputation: 7728

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

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 ?

Upvotes: 10

Views: 6894

Answers (8)

raton
raton

Reputation: 428

python 3.2

next(i for  i in arr if i>320)

Upvotes: 2

Love Bisaria
Love Bisaria

Reputation: 167

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:
        num = modBinarySearch(arr[0:mid],x)
    else:
        num = modBinarySearch(arr[mid:l],x)
    return num

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

Upvotes: 0

the wolf
the wolf

Reputation: 35532

The bisect module is your best choice for this:

from bisect import bisect_left, bisect_right

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


def find_lt(a, x):
    'Find rightmost value less than x'
    i = bisect_left(a, x)
    if i:
        return a[i-1]
    raise ValueError

def find_gt(a, x):
    'Find leftmost value greater than x'
    i = bisect_right(a, x)
    if i != len(a):
        return a[i]
    raise ValueError

print find_lt(arr,320)          
print find_gt(arr,320)

prints 

313
353

Upvotes: 1

NPE
NPE

Reputation: 500357

There is a standard module, bisect, that does this already:

In [49]: arr[bisect.bisect(arr, 320)]
Out[49]: 353

I think this should be the go-to method for searching sorted lists. There are a few examples in the manual.

As to your implementation, there is a number of problems:

  1. Your recursion doesn't handle small arrays correctly.
  2. The slicing done in the second branch is incorrect.
  3. Your function doesn't return anything.
  4. Because arr is in ascending order, arr[mid]>x and arr[mid-1]>x is equivalent to arr[mid-1]>x, suggesting you didn't write what you meant

Last but not least, recursion and all that slicing are completely unnecessary for this problem.

Upvotes: 11

Chocolava
Chocolava

Reputation: 1486

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)

Upvotes: 5

Danil Speransky
Danil Speransky

Reputation: 30453

def modBinarySearch(arr, n):
    m = len(arr) / 2

    if arr[m] >= n and arr[m - 1] < n:
        return arr[m]
    elif arr[m] > n and arr[m - 1] > n:
        return modBinarySearch(arr[:m], n)
    else:
        return modBinarySearch(arr[m:], n)


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

Upvotes: 3

arynaq
arynaq

Reputation: 6870

IF the list is sorted:

x = range(20)
N= 15

for i in x:
    if i>N:
        print i
        break

Gives 16.

If using numpy:

x = np.arange(20)
N = 15
x[x>15][0]

Gives 16.

If you were looking for easy implementations, for your specific problem, let me get back on that.

Upvotes: 0

paxdiablo
paxdiablo

Reputation: 881463

If the size of your lists is going to be 15, ditch the binary search altogether and use a sequential search.

You'll find the code much easier to write and, unless you need to do it many millions of times per second, the sequential solution will be more than fast enough.

If you do need to stick with the binary search, your first step should be to actually return the results of your recursive calls.

Upvotes: 6

Related Questions