Binary Search

Overview

Binary Search is an efficient algorithm used to find the position of a target value within a sorted dataset. It works by repeatedly dividing the search interval in half, and comparing the middle element of the interval with the target value. Binary Search is much faster than Linear Search for large datasets.

How Binary Search Works

• Pre-condition: The data must be sorted.
• Process:
  1. Identify the middle element of the dataset.
  2. Compare the middle element with the target value:
  • If it matches, the target is found.
  • If the target is smaller, restrict the search to the left half.
  • If the target is larger, restrict the search to the right half.
  3. Repeat the process until the target is found or the interval is empty.

Time Complexity

• Best Case: O(1) (target is the middle element).
• Worst Case: O(log n) (halves the search space with each step).
• Space Complexity:
  • O(1) for iterative implementation.
  • O(log n) for recursive implementation due to call stack.

Pseudocode for Binary Search

Iterative Approach:

METHOD BinarySearch(array, target)
    low ← 0
    high ← array.length - 1

    WHILE low <= high
        mid ← (low + high) DIV 2
        IF array[mid] = target
            RETURN mid
        ELSE IF array[mid] < target
            low ← mid + 1
        ELSE
            high ← mid - 1
    ENDWHILE

    RETURN -1  // Target not found

Recursive Approach:

METHOD BinarySearchRecursive(array, target, low, high)
    IF low > high
        RETURN -1  // Target not found

    mid ← (low + high) DIV 2
    IF array[mid] = target
        RETURN mid
    ELSE IF array[mid] < target
        RETURN BinarySearchRecursive(array, target, mid + 1, high)
    ELSE
        RETURN BinarySearchRecursive(array, target, low, mid - 1)

Python Example

Iterative Implementation:

def binary_search(array, target):
    low = 0
    high = len(array) - 1

    while low <= high:
        mid = (low + high) // 2
        if array[mid] == target:
            return mid
        elif array[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1  # Target not found

# Example usage:
data = [2, 4, 7, 10, 15, 18, 20, 25, 30]
print(binary_search(data, 18))  # Output: 5

Recursive Implementation:

def binary_search_recursive(array, target, low, high):
    if low > high:
        return -1  # Target not found

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

# Example usage:
data = [2, 4, 7, 10, 15, 18, 20, 25, 30]
print(binary_search_recursive(data, 18, 0, len(data) - 1))  # Output: 5

Tracing Binary Search

Note Summary