Mastering Search: A Guide to Implementing Binary Search Algorithm in Python

Codes With Pankaj

Introduction:

In the realm of computer science and algorithms, efficient searching is a fundamental skill. One of the most powerful and widely used searching techniques is the Binary Search algorithm. In this codeswithpankaj blog post, we’ll delve into the inner workings of Binary Search and provide a step-by-step guide on how to implement it in Python.

Understanding Binary Search:

Binary Search is a divide-and-conquer algorithm used to efficiently locate a target value within a sorted collection, such as an array. The key idea behind Binary Search is to repeatedly divide the search space in half, narrowing down the possible locations for the target.

Algorithm Steps:

1. Initialize Pointers :

• Start with two pointers, left and right, pointing to the first and last elements of the array, respectively.
• Calculate the middle index as mid = (left + right) // 2.

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
 ^                         ^
left                     right
mid = (left + right) // 2

2. Compare and Narrow Down :

• Compare the middle element with the target value.
• If they are equal, the target is found, and the index is returned.
• If the middle element is less than the target, update left to mid + 1 (disregard the left half).
• If the middle element is greater than the target, update right to mid - 1 (disregard the right half).

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
             ^       ^
            left   right
            mid = (left + right) // 2
              |
            Target

3. Repeat :

• Repeat steps 1 and 2 until the target is found or the search space is empty (left > right).

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
                     ^
                    left
                    right
                   mid = (left + right) // 2

flowchart

+---------------------+
| Start               |
+---------------------+
         |
         v
+---------------------+
| Initialize Pointers |
| left, right         |
| mid = (left+right)/2|
+----------+----------+
           |
           v
+---------------------+
| Compare and Narrow  |
| Down                |
| If arr[mid] == target|--------+
|   Return mid         |        |
| If arr[mid] < target |        |
|   Update left to     |        |
|   mid + 1            |        |
| If arr[mid] > target |        |
|   Update right to    |        |
|   mid - 1            |        |
+----------+----------+         |
           |                    |
           v                    |
+---------------------+         |
| Repeat              |<--------+
| Until left > right  |
+---------------------+
         |
         v
+---------------------+
| Target not found    |
| Return -1           |
+---------------------+
         |
         v
+---------------------+
| Target found        |
| Return index        |
+---------------------+
         |
         v
+---------------------+
| End                 |
+---------------------+

Python Implementation :

# www.codeswithpankaj.com
def binary_search(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2

        if arr[mid] == target:
            return mid  # Target found at index 'mid'
        elif arr[mid] < target:
            left = mid + 1  # Disregard left half
        else:
            right = mid - 1  # Disregard right half

    return -1  # Target not found in the array

# Example usage:
sorted_array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
target_value = 7
result = binary_search(sorted_array, target_value)

if result != -1:
    print(f"Element {target_value} found at index {result}.")
else:
    print(f"Element {target_value} not found in the array.")

Conclusion

Binary Search is a powerful algorithm known for its efficiency, especially when dealing with large sorted datasets. By dividing the search space in half with each iteration, it quickly zeroes in on the target value. This Python implementation provides a foundation for mastering the Binary Search algorithm and can be applied in various scenarios to optimize searching tasks.