CODEWITHSUNDEEP
pythonalgorithm
Lin Ma
Lin Ma

Reputation: 10139

find upper and lower bound value using binary search

Here is the code for binary search, wondering if there is no match value, the question is the upper bound should be positioned at either small or small+1? And lower bound should be located at small or small-1, correct? Thanks.

def binary_search(my_list, key):
    assert my_list == sorted(my_list)

    large = len(my_list) -1
    small = 0

    while (small <= large):
        mid = (small + large) // 2 )
        # print small, mid, large, " - ", my_list[mid], "~", key
        if my_list[mid] < key:
            small = mid + 1
        elif my_list[mid] > key:
            large = mid - 1
        else:
            return mid

    raise ValueError

Upvotes: 1

Views: 6001

Answers (2)

Brent Washburne
Brent Washburne

Reputation: 13138

@Paul is close, it should return mid+1 for the upper value. Instead of raising an exception, here is the code in Python that will return the lower and upper values:

value = my_list[mid]
lower = mid if value < key else mid-1
upper = mid if value > key else mid+1
return (lower, upper)

Here is an even simpler answer:

return (small-1, small)

Because small ends up above the key's index when you're looking for it, the lower bound is small-1 and the upper bound is small.

Upvotes: 1

user4668606
user4668606

Reputation:

That's not that simple. You'll have to take account of the fact, that the algorithm might either approximate the position of the searched item from the left (lower values) or right (higher values), which can't be determined after exiting the while-loop. Thus you'll have to check whether the value at mid is smaller or greater than the key:

lower = (my_list[mid] < key ? my_list[mid] : my_list[mid - 1]);
upper = (my_list[mid] > key ? my_list[mid] : my_list[mid + 1]);

Upvotes: 1

Related Questions