CODEWITHSUNDEEP
pythonbinary-search
Liondancer
Liondancer

Reputation: 16469

returning lower number in binary search if value cannot be found

I have a list of sorted numbers. [1,2,4,6,10,12]

I want to find a number within the list. If I cannot find it, I want to return the next lowest number.

For instance, n = 8. I search for 8 but cannot find it. I will then return 6 because it is the next lowest number.

I have some code but I can't seem to get the indexing correct:

def search_val(data, n):
    low = 0
    high = len(data) - 1
    if data[-1] <= n:
        return data[-1]
    if data[0] >= time:
        return

    while low < high:
        mid = (low + high) / 2
        if data[mid] == n:
            return data[n]
        if data[mid] > n:
            high = mid -1
        if data[mid] < n:
            low = mid + 1
    if data[low] < n:
        return data[low]
    else:
        return data[low - 1]

Upvotes: 0

Views: 270

Answers (2)

Tom Karzes
Tom Karzes

Reputation: 24052

This will fix all your problems, and should be a little faster:

def search_val(data, n):
    low = 0
    high = len(data) - 1

    while low <= high:
        mid = (low + high) // 2

        if data[mid] > n:
            high = mid -1
        elif data[mid] < n:
            low = mid + 1
        else:
            return data[mid]

    # Now low > high

    if high >= 0:
        return data[high]

    # All values are > n.  Just return the first.  Could
    # be changed to return None.

    return data[0]

Note that, in the case where all values are > n, it returns the first value. You could of course change it to return None instead if desired.

Also note that it assumes len(data) is >= 1. If that isn't always the case, you could add a check at the top and return None if data is the empty list.

Upvotes: 2

aghast
aghast

Reputation: 15300

Is the list guaranteed to be in order? If not, try this:

data = [1,2,4,6,10,12]
result = max((n for n in data if n <= 8))

Upvotes: 1

Related Questions