# Get an integer from the user
# This function always returns an integer. It will keep looping until
# a valid integer is typed.
def GetInt():
while True:
s = input()
try:
i = int(s)
return i
except:
print("You entered an invalid number. Please try again.")
# Initialise the list of numbers
def InitList(List):
List.clear()
for i in range(LEN_LIST):
List.append(i)
# Linear search
def LinearSearch(List, SearchFor):
found_at = -1
for i in range(LEN_LIST):
if List[i] == SearchFor:
found_at = i
break
if found_at >= 0:
print("Found at position %d in the list" % (i,))
else:
print("Not found")
print("")
# Binary search
def BinarySearch(List, SearchFor):
# if the number to find is less than the smallest number in our list
# or greater than the largest number then we know immediately it
# isn't in the list.
if SearchFor < List[0] or SearchFor > List[LEN_LIST-1]:
print("Not found")
return
# left_end is the start of the section we are checking and right_end
# is the end of the section we are checking. mid_point is the middle
# item in the section.
left_end = 0
right_end = LEN_LIST-1
# We keep searching until we get down to a section of length 2
# We stop at this point because a section of length 2 doesn't have
# a mid point
while right_end - left_end > 1:
mid_point = int((left_end + right_end)/2)
if SearchFor <= List[mid_point]:
right_end = mid_point
else:
left_end = mid_point
# We reduced the section to two items so check if either matches the
# number we are searching for
if SearchFor == List[left_end]:
print("Found at position %d in the list" % (left_end,))
elif SearchFor == List[right_end]:
print("Found at position %d in the list" % (right_end,))
else:
print("Not found")
print("")
# Main
LEN_LIST = 20
mylist = []
InitList(mylist)
print(mylist)
print("Number to search for: ")
i = GetInt()
LinearSearch(mylist, i)
BinarySearch(mylist, i)