How to fix this algorithm?

Question

Python

I can not understand why the algorithm does not work:

def binary_search(lst,x):
  start = 0
  finish = len(lst)
  while start < finish:
    mid = (start + finish)//2
    guess = lst[mid]
    if guess == x:
      return mid
    if guess > x:
      finish = mid - 1
    else:
      start = mid + 1

x = []
for i in range(1,101):
  x.append(i)
binary_search(x,12)
input()

Answer 1

What is difficult right now? and "Senior Python developer" can't debug? Well, at least arrange the prints in order to see the execution steps, but rather master pdb.

Answer 2

1) to begin with, indent 4 spaces as written in pep8
2) secondly, write what exactly you expect from your algorithm, and what you think it does wrong

Answer 3

Decide on the meaning of start and finish. start is the first element of the range that the x you are looking for can be in. finish, judging by the fact that it is equal to len(lst) first - this is after the end of the interval (not included in it).
So, based on this, it is necessary to drive the cycle while start < finish - this is correct.
When going up, you need to start doing mid + 1 - that's right.
When going down, you need to finish doing mid - this is a mistake! After all, you throw away the element just considered, since it did not fit. But the previous one behind it may be the desired one. You can't do finish = mid-1 - you lose a potentially important element.
Another fix is ​​to change the meaning of finish to be the end of the segment inclusive. Then the assignments in the loop are correct, but the loop condition and initialization are wrong. You need to run the loop while start <= finish and initially assign len(lst)-1.