Why am I not able to get the last number from list using binary search?

Question

I've written a code to find the index place of the number asked by user. I am getting the answer for all numbers except the last number (after sorting the list) which is 92 in this case, below is the code. Please guide what is wrong here.

# Python program to implement binary search

list = [54, 67, 85, 33, 92, 74]
list.sort()
print(f'Given list is: {list}')

low = 0
upp = len(list)-1
mid = (low + upp) // 2

num = list.index(int(input('Enter number: ')))

while num != mid:
    mid = (low + upp) // 2
    if num < mid:
        upp = mid
        mid = (low + upp) // 2
    else:
        if num > mid:
            low = mid
            mid = (low + upp) // 2
print(f'found at {mid} index')

`num = list.index(int(input('Enter number: ')))` uses the actual index to calculate the index. That's not what you want. Also shouldn't use the built-in `list` as a variable name. — Mark Tolonen, Jun 21 '22 at 18:15
`num = list.index(int(input('Enter number: ')))` is getting you the index directly, with `O(n)` search. The rest of your code isn't even looking at your `list` (which should *not* be named `list`, since it cuts off access to the built-in `list` constructor). The rest of your code is confusingly binary searching for the index it already knows (it's in `num`). — ShadowRanger, Jun 21 '22 at 18:18
Also, presumably `upp` should be initialized to `len(list)`, not `len(list) - 1` (I haven't analyzed things thoroughly, but most binary search algorithms use an exclusive index for the upper bound; the fact you don't, and fail only when searching for the largest value, indicates you probably *should* be using `len(list)`). — ShadowRanger, Jun 21 '22 at 18:20
Hint: does it not seem strange to you, that none of the code inside the loop does anything involving the list? — Karl Knechtel, Jun 21 '22 at 18:31

ShadowRanger · Answer 1 · 2022-06-21T19:06:10.463

Your described problem is that the algorithm you're using is intended to have upp as the exclusive upper bound; by initializing it to len(list)-1, you can't find the uppermost index at all. Change upp = len(list)-1 to upp = len(list) and the code "works" (it just doesn't do anything useful).

Your other problems are:

num = list.index(int(input('Enter number: '))) is getting you the index directly, with O(n) search under the hood, eliminating the benefit of binary searching. The rest of your code isn't even looking at your list, you're just doing O(log n) work to find a mid equal to num, when mid = num would achieve the same result with no search involved (no additional search beyond what list.index was doing anyway).
You named your variable list, which means the list constructor is unavailable; this is a bad idea (even if it doesn't break anything here).
(Not an issue in the current code, but an issue trying to fix #1) Your code experiences an infinite loop when the value being searched for is not in the list (in your current code, the list.index call handles that by raising an exception, but as noted, if you use list.index, you gain no benefit from binary search at all).

For #1, you wanted to accept the input without a list.index call:

num = int(input('Enter number: '))

then change each comparison between num and mid to compare num and list[mid] (or mylist[mid] or whatever better name you use for the list), so num is always the value being searched for, mid is the current index being searched, and list[mid] is the value at that index. You also need to improve your search so it stops when the value you're searching for doesn't exist in the list (left as exercise; there's thousands upon thousands of examples of hand-implemented binary search, in pseudocode and Python, out there), rather than looping forever.

score 0 · Answer 2 · answered Jun 21 '22 at 18:26

Here's a binary search implementation that may help you to see where you've gone wrong:

list_ = sorted([54, 67, 85, 33, 92, 74])

def bsearch(lst, x):
    L = 0
    R = len(lst) - 1
    while L <= R:
        m = (L + R) // 2
        if (v := lst[m]) == x:
            return m
        if v < x:
            L = m + 1
        else:
            R = m - 1
    return -1

while (x := input('Enter a number to search for (q to quit): ')) not in 'Qq':
    try:
        if (i := bsearch(list_, int(x))) < 0:
            print('Not found')
        else:
            print(f'Found at {i}')
    except ValueError as e:
        print(e)

Why am I not able to get the last number from list using binary search?

2 Answers2