🎯 Binary Search

The king of logarithmic algorithms. Master binary search and its variations for lightning-fast searches in sorted data.

Overview

ℹ️

Why Binary Search?

Linear search is O(n). Binary search is O(log n). For a million elements, binary search needs only 20 comparisons vs 500,000! It's the foundation for efficient searching in databases, file systems, and competitive programming.

Key Binary Search Variations

Basic Binary Search

Find exact element in sorted array. Return index if found, -1 otherwise.

Time: O(log n)Space: O(1)

First Occurrence

Find first occurrence of target in array with duplicates

Time: O(log n)Space: O(1)

Search in Rotated Array

Find element in rotated sorted array without duplicates

Time: O(log n)Space: O(1)

Interactive Visualizer

Binary Search Visualization

🎯

Basic Binary Search Visualizer

Watch the algorithm eliminate half the search space with each step.

Deep Dive: Basic Binary Search

Time Complexity

Time: O(log n)

Space Complexity

Space: O(1)

Prerequisite

Sorted Array

python

def binarySearch(arr, target):
    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

Initialize Pointers

Set left = 0, right = len(arr) - 1. These define the current search range.

Calculate Midpoint

mid = (left + right) // 2. Avoid overflow with: mid = left + (right - left) // 2.

Compare with Target

If arr[mid] == target, found! If arr[mid] < target, search right half. Otherwise search left half.

Update Boundaries

Move left or right pointer based on comparison. Continue until left > right or target found.

Common Binary Search Problems

Find First/Last Position

Medium

Adjust conditions to find first/last occurrence

Search in Rotated Array

Medium

Identify which half is sorted, adjust search

Find Peak Element

Medium

Use binary search to find peak (max element)

Search Insert Position

Easy

Return position where target should be inserted

Koko Eating Bananas

Medium

Binary search on answer space (speed)

Capacity to Ship

Medium

Binary search on weight capacity

Interview Questions

Why is binary search O(log n) not O(n/2)?

Big O notation describes asymptotic behavior. n/2 is still O(n) because it's linear in n. Binary search repeatedly divides by 2, needing log₂(n) iterations maximum.

What causes off-by-one errors in binary search?

Common mistakes: 1) mid = (left + right) / 2 (use // for integer), 2) wrong boundary updates (mid + 1 vs mid), 3) wrong loop condition (< vs <=).

Can binary search work on unsorted data?

No. Binary search's correctness depends on sorted property. On unsorted data, it may miss the target.

When do you use binary search vs hash table?

Hash table is O(1) average case, better for exact lookup. Binary search is O(log n) guaranteed, better when: data is pre-sorted, need range queries, memory-limited.

What's Next?

Advanced Concepts

Take your skills further with these advanced topics: