Design a modular program to perform a binary search in Python that includes IPO

Question

Design a modular program to perform a binary search in Python that includes IPO comments.. Your program should initialize an unsorted list (using the list provided), display the unsorted list, sort the list and display the sorted list. The program should then set up a loop to ask the user for a name, perform a binary search, and then report if the name is in the list. Use a sentinel value to end the loop.

Test list: [ 'Paul', 'Aaron', 'Jacob', 'James', 'Bill', 'Sara', 'Cathy', 'Barbara', 'Amy', 'Jill' ]

Select either the bubble sort or the insertion sort. Select either the iterative or recursive version of the binary search algorithm to implement.

Explanation / Answer

def display_list(test_list):
for item in test_list:
print(item, end=" ")
print()

def insertion_sort(test_list):
for i in range(1, len(test_list)):
key = test_list[i]
j = i-1
while j >=0 and key < test_list[j] :
test_list[j+1] = test_list[j]
j -= 1
test_list[j+1] = key

def binarySearch(test_list, x):
l = 0
r = len(test_list)
while l <= r:
mid = l + (r - l)//2;
if test_list[mid] == x:
return mid
elif test_list[mid] < x:
l = mid + 1
else:
r = mid - 1
  
return -1

def main():
test_list = [ 'Paul', 'Aaron', 'Jacob', 'James', 'Bill', 'Sara', 'Cathy', 'Barbara', 'Amy', 'Jill' ]
print("Unsorted list: ")
display_list(test_list)
  
  
insertion_sort(test_list)
  
print("Sorted list: ")
display_list(test_list)
  
while True:
item = input("Enter a name to search: ")
item = item.strip()
ind = binarySearch(test_list, item)
if ind != -1:
print(item + " found at index " + str(ind))
else:
print(item +" is not found.")
choice = input("Do you want to exit (y/n)? ")
if choice == "y":
break
  

if __name__ == '__main__':
main()

# copy pastable code link: https://paste.ee/p/TVPfZ

Sample run

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.