Binary Search on Arrays

Efficient searching in sorted arrays using divide and conquer. Master the classic binary search algorithm.

Binary search is one of the most fundamental algorithms in computer science. It finds elements in a sorted array in O(log n) time by repeatedly halving the search space.

The Core Idea

Instead of checking every element (O(n)), binary search:

Looks at the middle element
If it's the target, we're done
If target is smaller, search the left half
If target is larger, search the right half
Repeat until found or search space is empty

Finding 23 in [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]:

Step 1: Check middle (16)
[2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
               ↑
            23 > 16, go right

Step 2: Check middle of right half (56)
[23, 38, 56, 72, 91]
          ↑
      23 < 56, go left

Step 3: Check middle of remaining (38)
[23, 38]
     ↑
  23 < 38, go left

Step 4: Check remaining (23)
[23]
  ↑
 Found!

Implementation

Iterative (Preferred)

fn binary_search(arr: &[i32], target: i32) -> i32 {
    let mut left = 0;
    let mut right = arr.len() as i32 - 1;

    while left <= right {
        let mid = left + (right - left) / 2;  // Avoid overflow

        if arr[mid as usize] == target {
            return mid;
        } else if arr[mid as usize] < target {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    -1  // Not found
}

fn main() {
    let arr = vec![2, 5, 8, 12, 16, 23, 38, 56, 72, 91];
    println!("{}", binary_search(&arr, 23));  // 5
    println!("{}", binary_search(&arr, 25));  // -1
}

func binarySearch(arr []int, target int) int {
    left, right := 0, len(arr)-1

    for left <= right {
        mid := left + (right-left)/2

        if arr[mid] == target {
            return mid
        } else if arr[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

    return -1
}

Recursive

fn binary_search_recursive(arr: &[i32], target: i32, left: i32, right: i32) -> i32 {
    if left > right {
        return -1;
    }

    let mid = left + (right - left) / 2;

    if arr[mid as usize] == target {
        mid
    } else if arr[mid as usize] < target {
        binary_search_recursive(arr, target, mid + 1, right)
    } else {
        binary_search_recursive(arr, target, left, mid - 1)
    }
}

fn main() {
    let arr = vec![2, 5, 8, 12, 16, 23, 38, 56, 72, 91];
    println!("{}", binary_search_recursive(&arr, 23, 0, (arr.len() - 1) as i32));
}

Why left + (right - left) // 2?

Using (left + right) // 2 can cause integer overflow in languages like C/C++ when left and right are large. The alternative formula avoids this issue while giving the same result.

Time Complexity

Each iteration halves the search space:

n → n/2 → n/4 → ... → 1

Number of iterations: O(log n)

n = 1,000,000 elements
Binary search: ~20 comparisons (log₂ 1,000,000 ≈ 20)
Linear search: up to 1,000,000 comparisons

Space Complexity

Iterative: O(1)
Recursive: O(log n) for call stack

Common Mistakes

1. Off-by-One Errors

// Wrong: might skip elements
while left < right {  // Should be left <= right

// Wrong: infinite loop
left = mid;  // Should be left = mid + 1

// Wrong: infinite loop
right = mid;  // Should be right = mid - 1

2. Unsorted Array

Binary search requires a sorted array. If unsorted, results are undefined.

3. Integer Overflow

// Potentially overflows in some languages
let mid = (left + right) / 2;

// Safe version
let mid = left + (right - left) / 2;

Binary Search Template

A robust template for binary search:

fn binary_search_template(arr: &[i32], target: i32) -> i32 {
    let mut left = 0;
    let mut right = arr.len() as i32 - 1;

    while left <= right {
        let mid = left + (right - left) / 2;

        if arr[mid as usize] == target {
            return mid;  // Found
        } else if arr[mid as usize] < target {
            left = mid + 1;  // Search right
        } else {
            right = mid - 1;  // Search left
        }
    }

    -1  // Not found
}

Key invariants:

left and right define the current search range (inclusive)
left <= right ensures we don't miss elements
mid + 1 and mid - 1 ensure progress (avoid infinite loops)

Standard Library Functions

Most languages provide built-in binary search:

use std::cmp::Ordering;

fn main() {
    let arr = vec![1, 3, 5, 7, 9, 11];

    // Find using binary_search
    match arr.binary_search(&5) {
        Ok(index) => println!("Found at index: {}", index),  // 2
        Err(index) => println!("Not found, would insert at: {}", index),
    }

    match arr.binary_search(&6) {
        Ok(index) => println!("Found at index: {}", index),
        Err(index) => println!("Not found, would insert at: {}", index),  // 3
    }
}

import "sort"

arr := []int{1, 3, 5, 7, 9, 11}
idx := sort.Search(len(arr), func(i int) bool {
    return arr[i] >= 5
})
// idx = 2

Real-World Applications

Dictionary/Phonebook Lookup

Finding a word in a sorted dictionary is binary search.

Database Indexes

B-trees use binary search principles for fast lookups.

Git Bisect

Finding the commit that introduced a bug:

git bisect start
git bisect bad      # Current commit is bad
git bisect good v1.0  # v1.0 was good

# Git uses binary search to find the first bad commit

Debugging

"Does the bug exist in the first half of the code? No? Then check the second half..."

Time Comparison

| Array Size | Linear Search | Binary Search | |------------|---------------|---------------| | 10 | 10 | 4 | | 100 | 100 | 7 | | 1,000 | 1,000 | 10 | | 1,000,000 | 1,000,000 | 20 | | 1,000,000,000 | 1,000,000,000 | 30 |

Prerequisite: Sorted Data

If your data isn't sorted, you must either sort it first (O(n log n)) or use linear search. For a single search, linear is faster. For multiple searches, sorting once then binary searching repeatedly is more efficient.

Variations

Search in Rotated Sorted Array

fn search_rotated(nums: &[i32], target: i32) -> i32 {
    let mut left = 0;
    let mut right = nums.len() as i32 - 1;

    while left <= right {
        let mid = left + (right - left) / 2;
        let mid_idx = mid as usize;

        if nums[mid_idx] == target {
            return mid;
        }

        // Determine which half is sorted
        if nums[left as usize] <= nums[mid_idx] {
            // Left half is sorted
            if nums[left as usize] <= target && target < nums[mid_idx] {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else {
            // Right half is sorted
            if nums[mid_idx] < target && target <= nums[right as usize] {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }

    -1
}

Search 2D Matrix

fn search_matrix(matrix: &Vec<Vec<i32>>, target: i32) -> bool {
    if matrix.is_empty() {
        return false;
    }

    let rows = matrix.len();
    let cols = matrix[0].len();
    let mut left = 0;
    let mut right = (rows * cols - 1) as i32;

    while left <= right {
        let mid = left + (right - left) / 2;
        let mid_idx = mid as usize;
        let val = matrix[mid_idx / cols][mid_idx % cols];

        if val == target {
            return true;
        } else if val < target {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    false
}

Key Takeaways

Binary search finds elements in O(log n) time
Requires a sorted array
Iterative version preferred (O(1) space)
Use mid = left + (right - left) // 2 to avoid overflow
Watch for off-by-one errors: left <= right, mid + 1, mid - 1
Foundation for many advanced algorithms and data structures

Binary search is deceptively simple but easy to get wrong. Master the basic template, understand the invariants, and you'll be ready for the many variations used in interviews and real-world applications.

Bucket Sort

Binary Search Variations