C
C
Clazzer1232019-09-12 14:30:35
Python
Clazzer123, 2019-09-12 14:30:35

Don't understand part of the binary search algorithm?

There is a code

def binary_search(mylist, item):
    start = 0
    stop = len(my_list) - 1

    while start <= stop:
        mid = (start + stop) // 2
        guess = mylist[mid]
        if guess  == item:
            return mid
        if guess > item:
            stop = mid - 1
        else:
            start = mid + 1
    return None

my_list = [1,2,3,4,5,6,7,8,9,11,12,13,14,15,16,17,19]
print(binary_search(my_list, 3))

I can't understand why in the line
stop = len(my_list) - 1
do "-1"? why not just write stop = len(my_list)?

Answer the question

In order to leave comments, you need to log in

2 answer(s)
V
Vladimir Kuts, 2019-09-12
@fox_12

Probably because in an array, indices start from 0. And therefore, the index of the last element of the array will be equal to the length of the array minus 1
because in this case it is possible to crash with an error when accessing a non-existent element of the array

L
longclaps, 2019-09-12
@longclaps

That's why

def binary_search(mylist, item):
    start = 0
    stop = len(my_list) # верни -1

    while start <= stop:
        mid = (start + stop) // 2
        guess = mylist[mid]
        if guess  == item:
            return mid
        if guess > item:
            stop = mid - 1
        else:
            start = mid + 1
    return None

my_list = [1,2,3,4,5,6,7,8,9,11,12,13,14,15,16,17,19]
print(binary_search(my_list, 20))

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question