Iterative binary search in python

Question

in the conditionals why don't you have to write high = data[middle_term] - 1. I understand why you do it in the actual if/else statements

data = [1,2,3,6,9,12,15,18,20]
def binary_search_algorthim(data,target):
    low = 0
    high = len(data) - 1

    while low <= high:
        middle_term = (low + high) // 2
        if target == data[middle_term]:
            return True
        elif target < data[middle_term]:
            high = middle_term - 1
            print("high",high)
        elif target > data[middle_term]:
            low = middle_term + 1
            print("low", low)
    return False

Please format the code. select it and tytpe ctrl-k. Formatting help ... more Formatting ... Formatting sandbox — wwii
– wwii, Commented Sep 23, 2019 at 1:08
Visualize at : pythontutor.com/visualize.html#mode=edit. high,low, and middle_term are indices. data[middle_term] is a value at an index. you are keeping track of indices not values. — wwii
– wwii, Commented Sep 23, 2019 at 1:11
@Mohib Don't mean to be mean, but along the lines of @wwii's comment, code formatting also includes your code "high = data[middle_term] -1" above, which after adding ` ` becomes high = data[middle_term] -1. — Stoner
– Stoner, Commented Sep 23, 2019 at 2:00

lenik · Accepted Answer · 2019-09-23 02:10:18Z

1

high and low are not the actual numbers from your data, they just mark the place where the actual numbers are, so when you want to compare to target you don't compare the place and the value, you have to compare the value at the place and the value.

Hence, target (value) = data[ (position) ] (again, a value)

answered Sep 23, 2019 at 2:10

lenik

23.6k4 gold badges38 silver badges44 bronze badges

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

Collectives™ on Stack Overflow

Iterative binary search in python

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related