Binary Search Algorithm in Python

Introduction:

Binary search is a highly efficient search algorithm used to find a specific element within a sorted list. This tutorial provides a comprehensive guide to implementing the binary search algorithm in Python. You’ll learn the step-by-step process of binary search, its underlying logic, and how it quickly locates elements in a sorted list.

Code:

def binarySearch(list, key):
    # Initialize the pointers for the search range.
    first = 0
    last = len(list) - 1

    # Perform binary search while the search range is valid.
    while first <= last:
        # Calculate the index of the middle element in the current search range.
        mid = (first + last) // 2

        # If the middle element is equal to the key, the key is found at index 'mid'.
        if list[mid] == key:
            return mid

        # If the key is greater than the middle element, search the right half of the list.
        elif key > list[mid]:
            first = mid + 1

        # If the key is smaller than the middle element, search the left half of the list.
        elif key < list[mid]:
            last = mid - 1

    # If the key is not found within the loop, return -1 to indicate that it's not present in the list.
    return -1

list1 = []  # Create an empty list

# Ask the user to enter elements in ascending order, stop when they enter -999.
print("Create a list by entering elements in ascending order")
print("Press enter after each element, press -999 to stop")
num = int(input())
while num != -999:
    list1.append(num)
    num = int(input())

# Ask the user to enter the key they want to search for.
n = int(input("Enter the key to be searched: "))

# Call the binarySearch function with the list and key as arguments.
pos = binarySearch(list1, n)

# Check the result of the binarySearch function and print appropriate messages.
if pos != -1:
    print(n, "is found at position", pos + 1)
else:
    print(n, "is not found in the list")

Logic:

1. Define the binarySearch function that takes a list list and a search key as input.
2. Initialize the search range pointers first and last to the beginning and end of the list, respectively.
3. Perform binary search while the search range is valid (first is less than or equal to last).
4. Calculate the index of the middle element using integer division.
5. Compare the middle element with the search key.
6. If they are equal, return the index mid indicating the key’s position.
7. If the key is greater, adjust the search range to the right half of the list.
8. If the key is smaller, adjust the search range to the left half of the list.
9. If the key is not found within the loop, return -1 to indicate its absence in the list.

Output:

>>Create a list by entering elements in ascending order

>>Press enter after each element, press –999 to stop

>>1

>>3

>>5

>>7

>>9

>>11

>>13

>>15

>>-999

>>Enter the key to be searched: 7

>>7 is found at position 4