Performing A Binary Search

Introduction

"Binary search is an efficient search algorithm used to find the position of a target value within a sorted array. It works by repeatedly dividing the search interval in half. Binary search is particularly useful when dealing with large datasets because it has a time complexity of O(log n), where n is the number of elements in the array."

Understand the Problem

"To understand binary search, let's consider a scenario where we have a sorted array of elements. Our goal is to find the position (index) of a specific value within this array."

The Search algorithm

  1. Initialization:

    • Begin with the entire sorted array.
    • Set two pointers, low and high, to the first and last indices of the array, respectively.

  2. Iteration:

    • Repeat the following steps until the low pointer is less than or equal to the high pointer:
      • Calculate the middle index as (low + high) // 2.
      • Compare the value at the middle index with the target value:
        • If the middle value is equal to the target, return the middle index (found the target).
        • If the middle value is less than the target, update low to mid + 1 (search the right half).
        • If the middle value is greater than the target, update high to mid - 1 (search the left half).

  3. Termination:

    • If the low pointer exceeds the high pointer, the target value is not present in the array. Return -1 (not found).

  4. Code Implementation:

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
            
    return -1

# Example usage:
arr = [1, 3, 5, 7, 9, 11, 13]
target = 7
result = binary_search(arr, target)
if result != -1:
    print(f"Element {target} found at index {result}")
else:
    print("Element not found")
  1. Example:

"For example, let's search for the value 7 in the sorted array [1, 3, 5, 7, 9, 11, 13]."

  • Start with low = 0 and high = 6.
  • First iteration: mid = (0 + 6) // 2 = 3. The value at index 3 is 7, so we found the target.
  • Return the index 3.

Conclusion

"In conclusion, binary search is a powerful algorithm for efficiently finding values in sorted arrays. By repeatedly dividing the search space in half, binary search achieves logarithmic time complexity, making it suitable for searching large datasets quickly and effectively."