Different binary search outputs even though the list stays about the same

AHM Mamun 0
Viewed 20

I'm new to python and trying to understand binary searching. I wrote a code in which inventory is an array of 5 elements and input a particular item and then search the item using the binary search technique. This is my code:

inventory=["10", "50", "100", "150", "200"]

SearchItem=input("Enter item: ")

LB=0
UB=len(inventory)-1
Found=False

while Found==False and LB <= UB:
    Mid=(LB + UB)//2
    if inventory[Mid]==SearchItem:
        print("Item found in the position: ", Mid + 1)
        Found=True
    elif SearchItem>inventory[Mid]:
        LB= Mid + 1
    else:
        UB= Mid - 1

if Found==False:
    print("Item doesn't exist.")

What's the need for -1 in len(inventory)-1? I was trying to find out what the -1 meant here but am coming across more complicated codes.

How does SearchItem know if SearchItem is > or < inventory[Mid]? Cause if it does, shouldn't it be automatically known by inventory[Mid] where SearchItem is at? I also tried adding both integers and strings to the inventory as:

inventory=["a", "10", "50", "100", "200"]

and:

inventory=["10", "50", "100", "200", "a"]

but it comes with the following outputs respectively:

Enter item: a
Item found in the position:  5

.

Enter item: a
Item doesn't exist.

Why do these two inventories have different outputs? Cause if inventory[Mid] knows where SearchItem lies, shouldn't the position of a be found?

python
1 Answers

I do not know the answer to the question -1 of the length (it makes no sense) And the error that caused the code to not work was that you stored numbers in the array as strings Because of this, python compared values not as numbers, but as words (in lexicographic order) If you remove the quotes in the array declaration and add int() in the input line, then the code starts working as it should

Corrected code:

inventory = [10, 50, 100, 150, 200]

SearchItem = int(input("Enter item: "))

LB = 0
UB = len(inventory)
Found = False

while Found == False and LB <= UB:
    Mid = (LB + UB) //  2
    if inventory[Mid] == SearchItem:
        print("Item found in the position: ", Mid + 1)
        Found = True
    elif SearchItem > inventory[Mid]:
        LB = Mid + 1
    else:
        UB = Mid - 1

if Found ==  False:
    print("Item doesn't exist.")
Dmitrii Gavrilov0
Related