# Python Binary Search

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")

$$$$


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:
$$$$