Binary Search

Binary Search

Overview

Binary Search is an efficient algorithm used to find the position of a target element in a sorted array.
It follows the divide-and-conquer approach by repeatedly dividing the search interval in half.

Steps

  1. Start with the low and high indices (beginning and end of the array).
  2. Find the midpoint index.
  3. Compare the target with the midpoint element:
    • If equal → return the index.
    • If target < midpoint element → search the left half.
    • If target > midpoint element → search the right half.
  4. Repeat until the target is found or the interval is empty.

Example (Python – Iterative)

def binary_search_iterative(arr, target):
    low, high = 0, len(arr) - 1

    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid  # Target found
        elif arr[mid] < target:
            low = mid + 1  # Search right half
        else:
            high = mid - 1  # Search left half
    return -1  # Target not found


# Example usage:
arr = [1, 3, 5, 7, 9, 11]
print(binary_search_iterative(arr, 7))   # Output: 3
print(binary_search_iterative(arr, 4))   # Output: -1

Example (Python – Recursive)

def binary_search_recursive(arr, target, low, high):
    if low > high:
        return -1  # Base case: not found

    mid = (low + high) // 2

    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, high)
    else:
        return binary_search_recursive(arr, target, low, mid - 1)


# Example usage:
arr = [1, 3, 5, 7, 9, 11]
print(binary_search_recursive(arr, 9, 0, len(arr) - 1))   # Output: 4
print(binary_search_recursive(arr, 2, 0, len(arr) - 1))   # Output: -1

Key Points