# Binary Search Algorithm

No BS: It is important to try and implement known ‘easy’ algorithms as it provides practice on working towards trickier algorithms, as well as translating human instructions into a usable program.

With BS: Working through Exercise 20 of practicepython.org, you are tasked to implement the Binary Search Algorithm for a sorted list of numerical integers, and determine if a number exists in the list.

While you can easily implement Python’s built-in function of “if … in …:” but this doesn’t require much programming and being able to transform a set of seemingly logical and simple instructions into a program is always crucial.

If a client comes to you and says “I want a program to do X, if it can’t do X, then do Y, and if Y gives this result, try doing Z instead” then you need to be able to translate those instructions into something that Python (or whatever language you are using) can deal with.

```import random
import math

# Inputs:
# numlist - an ordered list
# N - a number to check if it is in 'numlist'

# Outputs: boolean - True/False
def inlist(numlist,N):

# Binary Search Algorithm
R = len(numlist)
L = 0

# If list is empty, return False
if L == R:
return False

# Define midpoint of search
while len(numlist) > 0:
R = len(numlist) # Upper limit of list
m = math.floor(R/2) # midpoint

if N < numlist[m] and N >= numlist:
# Define new lower list
numlist = numlist[L:m]

elif N > numlist[m] and N <= numlist[R-1]:
# Define new upper list
numlist = numlist[m:R]

elif N == numlist[m]:
return True
else:
return False

## MAIN PROGRAM ##

if __name__ == "__main__":

# Generate random list and sort it
L = []
for i in range(0,10):
L.append(random.randint(0,20))
L = sorted(L)

# User input for digit to check
N = int(input('I have a list of ten numbers from 0 to 20. What number should I check to see if it is included? '))

boolean = inlist(L,N)