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[0]:
         # 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)

   # Show answer
   if boolean == True:
      print(N,'is in the list, take a look...')
      print(L)
   else:
      print(N,'is not in the list, take a look...')
      print(L)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.