# Binary Search Algorithm

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.