Python binary search can not solve

Question

I am having troubles while learning binary search. Here is my code:

a = [1, 2, 4, 6, 7, 8, 11, 13, 23, 26, 28, 32, 36, 402, 2403, 3340, 4400]


def binary_search(list, whattosearch):
    start_index = 1
    end_index = len(list) - 1
    while True:
        mid_index = (end_index - start_index) // 2
        if mid_index < start_index or mid_index > end_index or mid_index < 0:
            return False

        mid_element = list[mid_index]
        if mid_element == whattosearch:
            return True
        if mid_element < whattosearch:
            start_index = mid_index
        else:
            end_index = mid_index

if __name__ == '__main__':
print(binary_search(a, 8))

I get 'False' as an output. Could someone help me, please?

as you run through the code, you get to a point where your end index is 7, your start index is 3, you set the midpoint as (end - start) // 2, so (7 - 3 ) // 2 thats 4 // 2 whic is 2. So you now have a midpoint less than your start point. And your code says if the mid is less than start return false — Chris Doyle
– Chris Doyle, Commented Dec 10, 2020 at 18:55
You should set the midpoint as the start point + the difference between the end and start point divided by 2. something like mid_index = start_index + ((end_index - start_index) // 2) — Chris Doyle
– Chris Doyle, Commented Dec 10, 2020 at 18:57

ssp · Accepted Answer · 2020-12-10 19:17:20Z

2

You shouldn't use list as a variable name since it's reserved for list type. start_index should be initialized to 0. Also a binary search shouldn't need a while True. In general:

# You can replace 
    while True:
# with:
    while start <= end:

# Remove
        if mid_index < start_index or mid_index > end_index or mid_index < 0:
            return False
# And add return False after the while loop.

# And use
            start = mid + 1  instead of start = mid
            end = mid - 1 instead of end = mid
# To avoid any indexing issues.

edited Dec 10, 2020 at 19:17

answered Dec 10, 2020 at 19:02

ssp

1,72013 silver badges17 bronze badges

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

Comments

HassanK · Accepted Answer · 2020-12-10 19:34:44Z

1

I have simplified your binary search code

a = [1, 2, 4, 6, 7, 8, 11, 13, 23, 26, 28, 32, 36, 402, 2403, 3340, 4400]


def binary_search(list, whattosearch):
    start_index = 0. # should not be 1
    end_index = len(list)
    while start_index<end_index:
        mid_index = (end_index + start_index) // 2
        mid_element = list[mid_index]
        if mid_element == whattosearch:
            return True
        if mid_element < whattosearch:
            start_index = mid_index + 1 # needs to move ahead of mid point
        else:
            end_index = mid_index
    return False

answered Dec 10, 2020 at 19:34

HassanK

807 bronze badges

Collectives™ on Stack Overflow

Python binary search can not solve

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related