Python Binary Search

Question

My take on a binary search algorithm without research or knowledge of an efficient one. It would be appreciated if one could show me an efficient way to do it using recursion or a more pythonic approach.

from math import *
numList = [i for i in range(11)]
while True:
 try:
 beginning = 0
 end = len(numList) - 1
 mid = floor(((end-beginning)/2) + beginning)
 value = int(input("What value would you like to search for?: "))
 notFound = True
 while notFound:
 if value > end or value < beginning:
 print("The value is not in the list")
 break
 elif value == mid:
 print("The value is in the list")
 print("The index is " + str(mid))
 notFound = False
 elif value == end:
 print("The value is in the list")
 print("The index is " + str(end))
 notFound = False
 elif value > mid:
 beginning = mid
 mid = floor(((end-beginning)/2) + beginning)
 elif value < mid:
 end = mid
 mid = floor(((end-beginning)/2) + beginning)
 except ValueError:
 print("Invalid characters")
```

Answer 1

numList is not used (this is "ok" as numList[i] == i). There is value == mid or value == end several times. But this just means you are comparing a value to be found with an index. The correct way would be value == numList[mid].

Consider using a function that does the binsearch for you.

You may or may not use recursion. There is a nice way to do binsearch without recursion.

I have also incorporated some naming conventions of python. If you are interested try programs like pylint. I have also added a bit nicer string formatting and some other python features you can live without but can come handy.

"""Binary search."""
from random import randint
def bin_search(sorted_list, to_find):
 """Searches the sorted_list for a to_find.
 If the to_find is found return (True, index)
 Otherwise return (False, 0)
 """
 beg = 0
 end = len(sorted_list) - 1
 while beg <= end:
 mid = (end + beg) // 2 # integer division
 if sorted_list[mid] == to_find:
 return (True, mid)
 if sorted_list[mid] < to_find:
 (beg, end) = (mid + 1, end)
 else: # sorted_list[mid] > to_find
 (beg, end) = (beg, mid - 1)
 return (False, 0)
# Create a sorted list of random numbers
MY_LIST = sorted(randint(0, 100) for _ in range(20))
print(MY_LIST)
while True:
 try:
 TO_FIND = int(input('Enter value you want to find: '))
 (FOUND, INDEX) = bin_search(sorted_list=MY_LIST, to_find=TO_FIND)
 if FOUND:
 print(f'Found {TO_FIND} at index: {INDEX}!')
 else:
 print(f'Value {TO_FIND} not found!')
 except ValueError:
 print('Invalid number to find')
```