Binary search a sorted list of integers in Python 3

Question

y is the value I am searching for. Is this the correct implementation for binary search?

y= 3
x= range(0,100)
left = 0
right = len(x)-1
mid=int((left+right)/2)
while x[mid]!=y:
 if x[mid]>y:
 right = mid
 mid=int((left+right)/2)
 if x[mid]<y:
 left = mid
 mid=int((left+right)/2)

• Bailey Parker: If you're using this code elsewhere and not implementing for the exercise, you should use the bisect module, which has functions which do this for you.

Answer 1

PEP-8

PEP-8 is a style guide for Python. It contains several practices which you should follow, like having spaces around operators. Use a tool, like pylint, to ensure you follow these practices.

Integer Division

mid=int((left+right)/2)

Python comes with a built-in integer division operator: //. You should use it.

mid = (left + right) // 2

Termination

while x[mid] != y:

You are searching until you find the desired value. What if the desired value is not present? You will search forever??? Consider adding a different stopping condition.

Redundancy

 if x[mid]>y:
 #...
 mid=int((left+right)/2)
 if x[mid]<y:
 #...
 mid=int((left+right)/2)

Since you are looping while x[mid] != y, your only real choices are for x[mid] > y or x[mid] < y. Instead of testing the second condition, how about using else:?

Since you enter will either the x[mid] > y then clause, or the x[mid] < y then clause, you will always be executing mid=int((left+right)/2). You can safely move those two statements out if the if, and unconditionally execute it at the end. As in:

 if x[mid] > y:
 #...
 else:
 #...
 mid = (left + right) // 2

Efficiency

If you start with left=0, right=99, mid=49, and find x[mid]>y is true, you proceed to search in the range left=0, right=49. But you've already tested x[49] and found the value wasn't there; you don't need to include it in your search range anymore. Similarly, when you find x[mid]<y, you don't need to include that mid point as the left end of your range.

 if x[mid] > y:
 right = mid - 1
 else:
 left = mid + 1

Bug

Your existing algorithm will not terminate for certain numbers. If you search for 99, the value of mid will take on the following values:

49, 74, 86, 92, 95, 97, 98, 98, 98, 98, 98, 98, 98, 98, ...