Binary search always returning number not found

Question

I'm trying to code this binary search algorithm but it is always returning -1 and the value is never found. What am i doing wrong? Thank you!

peso = [1,4,6,7,34,323,4333]

userInput = int(input("Ingresa peso a ver si esta ingresado"))
def binary_search(userInput):
    print(userInput)
    izq = 0
    der = len(peso)-1
    for i in range(0, len(peso)):
        medio = (izq+der)//2
        if medio == userInput:
            return medio
            break
        elif peso[medio] < userInput:
            izq = medio + 1
        elif peso[medio] > userInput:
            der = medio - 1
    return -1
value = binary_search(userInput)
print(value)

Have tried debugging your code, meaning go through it line by line and observing the values of your variables? — Mushroomator, Mar 01 '23 at 23:31
Yes, I added prints and it's always entering the "high" if statement — Lorenzo Durante, Mar 01 '23 at 23:32
Yes, so why would that be. You might wanna check the conditions before, particularly your `if` condition — Mushroomator, Mar 01 '23 at 23:34
Change `if medio == userInput:` to `if peso[medio] == userInput:`. And you can get rid of the unreachable `breal`, which serves no purpose. Also, the `for` loop makes no sense. Change it to `while izq <= der:`. — Tom Karzes, Mar 01 '23 at 23:36

Mushroomator · Accepted Answer · 2023-03-02T00:08:34.533

In order to solve your problem you need to check the value at the middle position (medio) not the calculated middle index itself. Then your program will return the correct result.

Additionally you could do some things to improve your program:

your break statement is unreachable as the return statement is before it, so you should remove it from your code
for loops are usually used to iterate over all items e.g. of a list. For iterating until a condition is met, one usually uses a while loop. It's more natural and makes reading the code a lot easier.
This is more of a theoretical point and does not really apply to Python (See SO Question - Integer overflow in Python3) but I wanted to include it anyway as it is something to generally consider when programming (in other languages): Your approach to calculating the middle could (theoretically) fail for two large integers as the result would overflow. You can use another approach which is not prone to this kind of problem by calculating the middle index using subtraction.

peso = [1, 4, 6, 7, 34, 323, 4333]


def binary_search(to_be_found):
    left = 0
    right = len(peso) - 1
    while left < right:
        middle = (right - left) // 2
        if peso[middle] < userInput:
            right = middle - 1
        elif peso[middle] > userInput:
            left = middle + 1
        else:
            return middle
    return -1


userInput = int(input("Please enter element to be found"))
print(binary_search(userInput))

Yes, good catch. Missed the unnecessary `elif`. I've removed it and also reordered the conditions to get the speedup in the average case. — Mushroomator, Mar 02 '23 at 00:10

Binary search always returning number not found

1 Answers1