linear_binary_compared

#-------------------------------------------------------------------------------
# Name:        module1
# Purpose:
#
# Author:      dgarey
#
# Created:     14/01/2020
# Copyright:   (c) dgarey 2020
# Licence:     <your licence>
#-------------------------------------------------------------------------------
from timeit import timeit
from random import randint

list_to_search = [i for i in range(1000000)]
#linear search
def linear_search (listnums,search):
    import random
    listnums = []
    for i in range(0,50): #will populate 50 random numbers
        listnums.append(random.randint(0,100)) # will select 50 random numbers between 1-100)
        listnums.sort()
print (listnums) #the numbers  randomly selected will appear below

print("what integer are you searching for between 1-100?")
search = int(input()) #requires user to input a number

found = False

for i in range (0,len(listnums)): # this checks from the first position in the random number list
  if listnums[i] == search: #if number entered is found in the list
    found = True

if found == True:
  print("this integer is in the list") #foundl
else:
  print("this integer is not in the list") #not found

  #Binary Search
def binary_search(listnums,search):
    found = False
    left = 0
    right = len(listnums)-1
    while left!=right:
        midpoint = (left + right)//2
        if listnums[midpoint] == search:
            found = True
            break
        if search <= listnums[midpoint]:
            right = midpoint
        else:
            left = midpoint+1
    return found,midpoint

import random
listnums = []
for i in range(0,50): #will populate 50 random numbers
  listnums.append(random.randint(0,100)) # will select 50 random numbers between 1-100)
  listnums.sort()
print(listnums) #the numbers  randomly selected will appear below

print("what integer are you searching for between 1-100?")
search = int(input()) #requires user to input a number

found,midpoint = binary_search(listnums,search)
print(found)
print(midpoint+1)

ls = lambda: linear_search(list_to_search, randint(0,1000000))
bs = lambda: binary_search(list_to_search, randint(0,1000000))

#time the functions for 100 runs each
print("Linear search took:")
print(timeit(ls, number = 100))

print("Binary search took:")
print(timeit(bs, number = 100))