Course contentsShow
← Computer Science
Lesson 251 of 2,8726. Arrays and Basic CollectionsFree lesson

Binary Search: Efficient Searching in Sorted Arrays

Use divide-and-conquer to search sorted arrays in O(log n) time by repeatedly halving the search space.

Binary Search: Efficient Searching in Sorted Arrays

You'll learn how to search a sorted array much faster than linear search by repeatedly cutting the search area in half.


The Core Idea

Imagine looking up a word in a physical dictionary. You don't start at page 1 and flip through every page—you open somewhere in the middle, see if your word comes before or after that page, then eliminate half the dictionary and repeat. Binary search works exactly the same way.

Requirements: Your array must be sorted first. That's the trade-off for speed.

How It Works

  1. Start by looking at the middle element of the array
  2. Compare it to your target value
  3. If it matches, you're done!
  4. If the target is smaller, discard the right half and repeat on the left half
  5. If the target is larger, discard the left half and repeat on the right half
  6. Continue until you find the target or run out of elements

Why It's Fast

Each comparison eliminates half of the remaining elements. This means:

  • 1,000 elements? Maximum 10 comparisons
  • 1,000,000 elements? Maximum 20 comparisons
  • Linear search would need up to 1,000,000 comparisons in the worst case!

This is called O(log n) time complexity—the time grows logarithmically with the array size, not linearly.

The Divide-and-Conquer Strategy

Binary search is your first encounter with divide-and-conquer: break a big problem into smaller pieces, solve the smaller piece, and ignore the rest. Each step divides the problem size by 2.


Key Takeaway: Binary search finds elements in sorted arrays in O(log n) time by repeatedly halving the search space, making it dramatically faster than linear search for large datasets.