loader

Updates

Algorithm: Binary Search

Explanation

  • Concept: Binary search is a highly efficient algorithm used to find a target value within a sorted array, narrowing down the search range by half each time.
  • Process: Binary search repeatedly divides the search interval in half. You start with two pointers, one at the beginning (left) and one at the end (right) of the array.
  • Steps:
    • In each iteration, calculate the middle index (mid = (left + right) // 2) and compare the middle element with the target value:
    • If the middle element equals the target, you've found it.
    • If it's less than the target, you narrow your search to the right half (i.e., set left to mid + 1).
    • If it's greater, you search the left half (i.e., set right to mid - 1).
  • Efficiency: Because the search space is halved each time, binary search has a time complexity of O(log n), which makes it very efficient for large datasets.

The brute force approach is simply a linear search—checking each element in the array sequentially until the target is found or the array is exhausted. This method does not leverage the sorted order of the array.

  • Time Complexity: O(n) because every element may need to be checked once.
  • Space Complexity: O(1) because it uses only a fixed number of variables without any additional data structures.

Algorithm Recap

  • Precondition: The input array must be sorted in ascending order.
  • Pointers: Use two pointers, 'left' and 'right', to represent the current search boundaries. (initially set to the start and end of the array, respectively).
  • Loop: While left is less than or equal to right, compute the mid index (mid = (left + right) // 2) and compare arr[mid] with the target. Adjust 'left' or 'right' based on this comparison:.
    • If arr[mid] equals the target: Return mid (the index of the target).
    • If arr[mid] is less than the target: The target must be in the right half, so update left to mid + 1.
    • If arr[mid] is greater than the target: The target must be in the left half, so update right to mid - 1.
  • Endcondition: When left > right, the search ends and the target is not found (return -1).

Considerations

  • When the number of elements is even, there are two middle elements; by using integer division, we pick the first one.
  • In many programming languages, compute mid as left + ((right - left) // 2) to avoid potential integer overflow.
  • In Python, integers can be arbitrarily large, so (left + right) // 2 is safe without overflow concerns.

Complexity Analysis

  • Time: O(log n) because with each iteration the search space is halved.
  • Space:

    O(1), as no additional data structures are used.

    • Iterative: Uses constant extra space, i.e. O(1), because it only employs a few variables without allocating additional data structures.
    • Recursive: Uses O(log n) space due to the recursion stack, with each recursive call adding a new frame proportional to the depth of the recursion.

Python Implementation

Python: 
      
          from typing import List

def binary_search(arr: List[int], target: int) -> int:
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

def run_algo():
    arr = [int(x) for x in input("Enter sorted array (space separated): ").split()]
    target = int(input("Enter target: "))
    res = binary_search(arr, target)
    print("Index of target:", res)

if __name__ == "__main__":
    run_algo()

Test Cases

  • Target in Middle

    Input:
    • Array: [1, 2, 3, 4, 5, 6, 7, 8, 9]
    • Target: 5
    Expected Output: 4
    Explanation: The target 5 is located at index 4 (using 0-based indexing).

  • Target is First Element

    Input:
    • Array: [1, 2, 3, 4, 5]
    • Target: 1
    Expected Output: 0
    Explanation: The target 1 is the first element, which is at index 0.

  • Target is Last Element

    Input:
    • Array: [1, 2, 3, 4, 5]
    • Target: 5
    Expected Output: 4
    Explanation: The target 5 is the last element, at index 4.

  • Target Not Present

    Input:
    • Array: [2, 4, 6, 8, 10]
    • Target: 7
    Expected Output: -1
    Explanation: Since 7 is not in the array, the function returns -1.

  • Single Element - Target Present

    Input:
    • Array: [10]
    • Target: 10
    Expected Output: 0
    Explanation: The only element is 10, located at index 0.

  • Empty Array

    Input:
    • Array: []
    • Target: 3
    Expected Output: -1
    Explanation: An empty array returns -1 because the target cannot be found.

Python Test Cases Implementation

Python: 
          def run_tests():
    tests = [
        {"arr": [1, 2, 3, 4, 5, 6, 7, 8, 9], "target": 5, "expected": 4},
        {"arr": [1, 2, 3, 4, 5], "target": 1, "expected": 0},
        {"arr": [1, 2, 3, 4, 5], "target": 5, "expected": 4},
        {"arr": [2, 4, 6, 8, 10], "target": 7, "expected": -1},
        {"arr": [10], "target": 10, "expected": 0},
        {"arr": [], "target": 3, "expected": -1},
    ]
    
    for i, test in enumerate(tests, 1):
        result = binary_search(test["arr"], test["target"])
        assert result == test["expected"], f"Test {i} failed: Expected {test['expected']}, got {result}"
        print(f"Test {i} passed.")

if __name__ == "__main__":
    run_tests()

Alternative Implementations

Alternative Approach (Minimizing Explicit Updates)

Python: 
              from typing import List

def binary_search(arr: List[int], target: int) -> int:
    left, right = 0, len(arr) - 1
    while (offset := (right - left) // 2) >= 0 and left <= right:
      mid = left + offset
      if arr[mid] == target:
          return mid
      left, right = (mid + 1, right) if arr[mid] < target else (left, mid - 1)
  return -1

def run_algo():
    arr = [int(x) for x in input("Enter sorted array (space separated): ").split()]
    target = int(input("Enter target: "))
    res = binary_search(arr, target)
    print("Index of target:", res)

if __name__ == "__main__":
    run_algo()

Key Points:

  • Using the offset variable: Instead of manually updating left and right, we calculate an offset for mid dynamically.
  • Tuple Assignment: The updates to left and right are now done in a more compact way using a tuple.

Recursive Binary Search

Python: 
              from typing import List

def binary_search_recursive(arr: List[int], target: int, left: int, right: int) -> int:
    if left > right:
        return -1  # Base case: target not found

    mid = (left + right) // 2

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

def binary_search(arr: List[int], target: int) -> int:
    return binary_search_recursive(arr, target, 0, len(arr) - 1)

def run_algo():
    arr = [int(x) for x in input("Enter sorted array (space separated): ").split()]
    target = int(input("Enter target: "))
    res = binary_search(arr, target)
    print("Index of target:", res)

if __name__ == "__main__":
    run_algo()

Key Points:

  • No Explicit Updates in a Loop: Instead of modifying left and right inside a loop, we let the function recursively call itself with new bounds.
  • Elegant and Functional: This follows the principle of recursion, keeping the function logic clean and concise.
  • Base Case Handling: When left > right, it immediately returns -1, avoiding unnecessary computations.

Considerations:

  • Recursion can cause stack overflow for very large arrays due to deep recursion depth.
  • Iterative binary search is generally more efficient in terms of memory (avoiding recursive calls).

Optimized Recursive (Tail-Call Avoidance)

Python: 
              from typing import List

def binary_search_tail_recursive(arr: List[int], target: int, left: int, right: int) -> int:
    while left <= right:  # Convert recursion into iteration
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1  # Shift search to the right half
        else:
            right = mid - 1  # Shift search to the left half
    return -1  # Not found

def binary_search(arr: List[int], target: int) -> int:
    return binary_search_tail_recursive(arr, target, 0, len(arr) - 1)

def run_algo():
    arr = [int(x) for x in input("Enter sorted array (space separated): ").split()]
    target = int(input("Enter target: "))
    res = binary_search(arr, target)
    print("Index of target:", res)

if __name__ == "__main__":
    run_algo()

Key Points:

  • Eliminates deep recursion: The function is rewritten to use a loop instead of repeated recursive calls.
  • Maintains functional style: It still follows the recursive thought process but avoids unnecessary stack frames.
  • Efficient and safe: Works even for very large arrays without stack overflow risks.

Benchmarking Code

Python: 
              import timeit
import bisect
from typing import List

# Tail-call avoidance version (loop-based recursion)
def binary_search_tail_recursive(arr: List[int], target: int, left: int, right: int) -> int:
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# Standard iterative binary search
def binary_search_iterative(arr: List[int], target: int) -> int:
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# Wrapper for the tail-recursive approach
def binary_search_tail(arr: List[int], target: int) -> int:
    return binary_search_tail_recursive(arr, target, 0, len(arr) - 1)

# Using the bisect module
def binary_search_bisect(arr: List[int], target: int) -> int:
    idx = bisect.bisect_left(arr, target)
    return idx if idx < len(arr) and arr[idx] == target else -1

# Test setup
small_array = list(range(10))           # Small (10 elements)
medium_array = list(range(1_000))       # Medium (1,000 elements)
large_array = list(range(1_000_000))    # Large (1,000,000 elements)

# Define search target (middle element for fair comparison)
target_small = small_array[len(small_array) // 2]
target_medium = medium_array[len(medium_array) // 2]
target_large = large_array[len(large_array) // 2]

# Benchmarking function
def benchmark():
    print("Testing on different array sizes...\n")

    for arr, target, size in [(small_array, target_small, "Small (10)"),
                              (medium_array, target_medium, "Medium (1,000)"),
                              (large_array, target_large, "Large (1,000,000)")]:
        
        t1 = timeit.timeit(lambda: binary_search_tail(arr, target), number=10000)
        t2 = timeit.timeit(lambda: binary_search_iterative(arr, target), number=10000)
        t3 = timeit.timeit(lambda: binary_search_bisect(arr, target), number=10000)

        print(f"Array Size: {size}")
        print(f"  Tail-Call Avoidance Recursive: {t1:.6f} sec")
        print(f"  Iterative Binary Search:       {t2:.6f} sec")
        print(f"  Bisect Module Search:          {t3:.6f} sec")
        print()

# Run benchmark
benchmark()

Key Points:

  • Iterative and Tail-Call Avoidance Perform the Same: Since both use a while loop, performance is nearly identical.
  • Bisect is Slightly Faster: Because bisect.bisect_left is optimized in C, it has a slight edge.

Considerations:

  • Recursive (Non-Tail-Optimized) is NOT Practical for Large Data

Test Script

Python: 
                from typing import List
import bisect

# Tail-call avoidance (loop-based) binary search
def binary_search_tail_recursive(arr: List[int], target: int, left: int, right: int) -> int:
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# Wrapper function for tail-recursive approach
def binary_search_tail(arr: List[int], target: int) -> int:
    return binary_search_tail_recursive(arr, target, 0, len(arr) - 1)

# Standard iterative binary search
def binary_search_iterative(arr: List[int], target: int) -> int:
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# Using the bisect module for reference
def binary_search_bisect(arr: List[int], target: int) -> int:
    idx = bisect.bisect_left(arr, target)
    return idx if idx < len(arr) and arr[idx] == target else -1

# Test function
def run_tests():
    tests = [
        {"arr": [1, 2, 3, 4, 5, 6, 7, 8, 9], "target": 5, "expected": 4},
        {"arr": [1, 2, 3, 4, 5], "target": 1, "expected": 0},
        {"arr": [1, 2, 3, 4, 5], "target": 5, "expected": 4},
        {"arr": [2, 4, 6, 8, 10], "target": 7, "expected": -1},
        {"arr": [10], "target": 10, "expected": 0},
        {"arr": [], "target": 3, "expected": -1},
    ]

    print("\nRunning tests...\n")
    
    for i, test in enumerate(tests, 1):
        for name, search_func in [
            ("Tail-Recursive (Loop-Based)", binary_search_tail),
            ("Iterative", binary_search_iterative),
            ("Bisect", binary_search_bisect),
        ]:
            result = search_func(test["arr"], test["target"])
            assert result == test["expected"], (
                f"Test {i} failed [{name}]: Expected {test['expected']}, got {result}"
            )
            print(f"Test {i} passed [{name}].")
    
    print("\nAll tests passed successfully!")

# Run tests when script is executed
if __name__ == "__main__":
    run_tests()

Test Results:

  • Tests All Three Approaches: Tail-Recursive (Loop-Based), Iterative, and Python's bisect
  • Covers Edge Cases: Empty arrays, single-element arrays, missing elements, etc
  • Asserts Correctness: Uses assert to enforce expected results
  • Clear Output: Each test case is labeled and outputs results neatly

Usage and Applications

  • Binary search is typically used on sorted arrays because the sorted order allows us to discard half the search space with each comparison. However, its application is not limited to arrays. You can use binary search in any scenario where you can make a binary decision to shrink the search range. This includes searching in binary search trees, solving optimization problems with monotonic conditions, and any other problem where the solution space can be efficiently partitioned into two halves.
XKCD

Explore further

Recursion Depth-First Search (DFS) Breadth-First Search (BFS) Binary Search
Linear Search Selection Sort Bubble Sort Merge Sort Quick Sort Insertion Sort Shell Sort Radix Sort
© 2025, Copyrights Open AGI Codes. All Rights Reserved, Built with Transforming Tomorrow, One Algorithm at a Time: The AI Revolution, on Pyramid by Pylons Project