Binary Search

Algorithms
principle

Also known as: bisection search, half-interval search

Grade 9-12

View on concept map

An efficient algorithm for finding a target value in a sorted list by repeatedly halving the search range. Binary search is orders of magnitude faster than linear search for large sorted datasets.

Definition

An efficient algorithm for finding a target value in a sorted list by repeatedly halving the search range. At each step, compare the target to the middle element: if equal, the search is done; if smaller, search the left half; if larger, search the right half.

💡 Intuition

Looking up a word in a dictionary: open to the middle, then go left or right depending on where your word falls.

🎯 Core Idea

Each comparison eliminates half the remaining possibilities — O(log n) vs O(n) for linear search.

Example

Find 37 in [1,5,12,23,37,49,56]: check middle (23), go right, check middle (49), go left, find 37.

Formula

O(\log n) time complexity

🌟 Why It Matters

Binary search is orders of magnitude faster than linear search for large sorted datasets. Searching 1 billion sorted items takes at most 30 comparisons with binary search, compared to up to 1 billion with linear search.

💭 Hint When Stuck

To perform binary search, set low = 0 and high = length - 1. Compute mid = (low + high) / 2. If the target equals the middle element, you are done. If the target is less, set high = mid - 1. If greater, set low = mid + 1. Repeat until found or low > high.

Formal View

Binary search on sorted array A[0..n-1] for target t: set l=0, r=n-1. While l \leq r, compute m = \lfloor(l+r)/2\rfloor. If A[m]=t, return m. If A[m]<t, set l=m+1. Else set r=m-1. Runs in O(\log n) time.

🚧 Common Stuck Point

Binary search only works on sorted data — applying it to unsorted data gives wrong results.

⚠️ Common Mistakes

  • Applying binary search to an unsorted list, which produces incorrect results
  • Computing the midpoint as (low + high) / 2, which can cause integer overflow—use low + (high - low) / 2 instead
  • Getting the boundary updates wrong (using mid instead of mid+1 or mid-1), causing infinite loops

Frequently Asked Questions

What is Binary Search in CS Thinking?

An efficient algorithm for finding a target value in a sorted list by repeatedly halving the search range. At each step, compare the target to the middle element: if equal, the search is done; if smaller, search the left half; if larger, search the right half.

What is the Binary Search formula?

O(\log n) time complexity

When do you use Binary Search?

To perform binary search, set low = 0 and high = length - 1. Compute mid = (low + high) / 2. If the target equals the middle element, you are done. If the target is less, set high = mid - 1. If greater, set low = mid + 1. Repeat until found or low > high.

Next Steps

linear search

How Binary Search Connects to Other Ideas

To understand binary search, you should first be comfortable with searching, array and efficiency. Once you have a solid grasp of binary search, you can move on to linear search.

← Back to Explorer