We’ll be looking at some algorithms. Say you have a large index of lastname, firstname pair arranged in alphabetical order and you want to search for a specific name. A linear search will get this done but as you scale up your application into hundreds of thousands or millions of records, it’s going to slow down significantly. A binary search will break guess the middle index of the list and if it is before at the entry it is looking for it will discard the lower half of the list if it’s ahead of the entry in alphabetical order it will discard top half of the list. Worst case scenario on a binary search of 300 records is that it takes 9 tries to get the correct record. A linear search would take a maximum of 300 tries. You can see at we scale up a binary search is much faster we had say 300,000 records rather than just 300. Here’s a Python program that generates 300 actual “lastname, firstname” pairs and then performs a binary search to find a specific entry while counting the number of tries it takes to locate the correct entry.

#!/usr/bin/python

import random
import time

# Generate a list of 300 "lastname, firstname" pairs
def generate_name_list():
# Sample lists of firstnames and lastnames
firstnames = ["John", "Jane", "Michael", "Emily", "William", "Olivia", "David", "Sophia", "James", "Ava"]
lastnames = ["Smith", "Johnson", "Brown", "Davis", "Miller", "Wilson", "Moore", "Anderson", "Taylor", "Clark"]

names = []
for i in range(300):
firstname = random.choice(firstnames)
lastname = random.choice(lastnames)
names.append(f"{lastname}, {firstname}")
return sorted(names) # Sort the list alphabetically

# Binary search function with try counting
def binary_search_with_count(arr, target):
left, right = 0, len(arr) - 1
tries = 0 # Initialize the try count

while left <= right:
mid = left + (right - left) // 2
tries += 1 # Increment the try count

if arr[mid] == target:
return mid, tries # Entry found, return its index and try count
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1

return -1, tries # Entry not found, return -1 and try count

# Generate the list of "lastname, firstname" entries
names_list = generate_name_list()

# Choose a random entry to search for
target_entry = random.choice(names_list)

# Perform binary search and count the number of tries
start_time = time.time()
index, tries = binary_search_with_count(names_list, target_entry)
end_time = time.time()

if index != -1:
print(f"Entry '{target_entry}' found at index {index} in {tries} tries.")
else:
print(f"Entry '{target_entry}' not found in the list in {tries} tries.")

print(f"Execution time: {end_time - start_time:.6f} seconds")

We have two lists, firstnames and lastnames, containing sample first names and last names.

The generate_name_list function randomly selects a first name and last name from these lists to create 300 “lastname, firstname” pairs. The list is then sorted alphabetically.

We randomly select an entry from the list to search for using the random.choice function.

We perform a binary search using the binary_search_with_count function, which not only returns the index of the found entry but also counts the number of tries it took to find it.

Finally, we print out whether the entry was found or not, along with the number of tries and the execution time of the search.