Finding the middle index value of an array in a binary search algorithm in Python

Question

I am new to Python and implementing a binary search algorithm. Here is the algorithm:

def binary_search(list, item):
    low = 0     
    high = len(list)-1

    while low <= high:
        mid = (low + high)
        guess = list[mid]

        if guess == item:
            return mid      
        if guess > item:
            high = mid - 1      
        else:
            low = mid + 1   
    return None

My question is in regard to the line mid = (low + high). The algorithm returns the correct index location for any item in the array whether I use mid = (low + high) or mid = (low + high)/2. Why is that? I have searched everywhere for an explanation for this specific question and cannot find one. All I've found is that Python 3 automatically rounds down numbers that are not evenly divisible, so for an array with an odd number of elements, like 13, the index of the middle element will be 6. But how does the algorithm above get to the middle index element without dividing by 2 every time?

Print out high, low, and mid at each step, and see what is happening. — cco
– cco, Commented Feb 7, 2019 at 23:21

Primusa · Accepted Answer · 2019-02-07 23:23:52Z

0

It's because your algorithm isn't a binary search.

mid = (low + high)

Since high starts at len(arr) - 1 and low always starts at 0 mid always starts at len(arr) - 1.

if guess > item:
    high = mid - 1

In this case in the next recalculation of mid the value of mid decreases by one. So if the guess is too high it goes down one element. The thing is since mid always starts at len(arr) - 1, this will always be True. guess will always start out as the largest element and then go down one by one. Until you hit:

if guess == item:
    return mid

In which case you just return the item. Your algorithm searches for the item linearly from the last element to the first in a one by one manner.

If you actually add a print(low, high, mid) you'll get an output like this:

answered Feb 7, 2019 at 23:23

Primusa

13.5k3 gold badges36 silver badges56 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

David Patrick Donohue Over a year ago

Thank you so much for that answer! What should I change to make it a binary search?

Primusa Over a year ago

mid = (high + low) / 2. You may have to work out a few bugs though, like high = mid - 1 should probably be high = mid. But there are plenty of binary search implementations online: geeksforgeeks.org/binary-search

Collectives™ on Stack Overflow

Finding the middle index value of an array in a binary search algorithm in Python

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related