Binary Search Algorithm in Python

1. Introduction

Binary Search is an efficient searching algorithm that works on the principle of divide and conquer. It requires the input list to be sorted. By repeatedly dividing the search interval in half, it drastically reduces the number of comparisons required to find an element, making it much faster than linear search for large datasets.

2. Implementation Steps

1. Find the middle element of the list.

2. Compare the search key with the middle element.

3. If they match, return the index of the middle element.

4. If the search key is less than the middle element, repeat the process with the left half of the list.

5. If the search key is greater than the middle element, repeat the process with the right half of the list.

6. If the list size reduces to 0, the element is not present in the list.

3. Implementation in Python

def binary_search(arr, x):
    """Function to perform Binary Search on a sorted list."""
    l = 0
    h = len(arr) - 1
    while l <= h:
        mid = (l + h) // 2
        if arr[mid] == x:
            return mid
        elif arr[mid] < x:
            l = mid + 1
        else:
            h = mid - 1
    return -1
arr = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
x = 12
result = binary_search(arr, x)
if result != -1:
    print(f"Element {x} is present at index {result}")
else:
    print(f"Element {x} is not present in the list")

Output:

Element 12 is present at index 5

Explanation:

1. The binary_search function initially defines low (l) and high (h) pointers representing the start and end of the list, respectively.

2. It then finds the middle index (mid) of the current interval.

3. It compares the middle element with the search key x.

4. If a match is found, it returns the index.

5. If x is greater, it updates the l pointer to mid + 1, effectively discarding the left half of the list.

6. If x is smaller, it updates the h pointer to mid - 1, discarding the right half.

7. The process repeats until the element is found or the size of the list interval becomes 0.

With each iteration, Binary Search halves the number of elements to be searched, resulting in a time complexity of O(log n), making it highly efficient for large datasets.

Related Data Structures in Python


Comments

Post a Comment