# Binary search a sorted list of integers in Python 3

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)

• 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. – Bailey Parker Feb 2 '19 at 6:59

## 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 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, ...