Binary Search Basics

A Smarter Way to Search

Imagine looking up a word in a physical dictionary. You wouldn't start at the first page and scan every word until you find it. Instead, you'd likely open the dictionary somewhere in the middle. If your word comes alphabetically after the words on that page, you'd focus on the second half of the book. If it comes before, you'd look in the first half. You'd repeat this process, narrowing down the search area each time until you pinpoint the exact page.

This intuitive process is the core idea behind binary search. It’s an efficient algorithm for finding a specific value within a sorted collection of items. The key word here is sorted. For this strategy to work, the data must be in a predictable order, just like the words in a dictionary.

Binary search is a classic "divide and conquer" algorithm. It repeatedly divides the problem into smaller, more manageable subproblems until a solution is found.

How It Works Step-by-Step

Let's walk through an example. Suppose we want to find the number 23 in this sorted list of numbers:

[4, 7, 10, 13, 16, 19, 22, 23, 26, 31, 35, 42]

To keep track of our search area, we'll use two pointers, low and high, which mark the beginning and end of the current search interval. Initially, low is at the first index (0) and high is at the last index (11).

Step 1: Find the middle First, we find the middle index of our search interval. We calculate this with mid = floor((low + high) / 2). In our case, (0 + 11) / 2 is 5.5, so the middle index is 5. The number at index 5 is 19.

Step 2: Compare and narrow Now we compare our target value, 23, to the middle value, 19. Since 23 is greater than 19, we know our target must be somewhere in the right half of the array. We can completely ignore the left half. We update our low pointer to mid + 1, so our new search interval is from index 6 to 11.

Step 3: Repeat the process We repeat the process with our new, smaller interval. The new middle index is floor((6 + 11) / 2), which is 8. The number at index 8 is 26. This time, our target 23 is less than 26. So, we discard the right half of this interval and update our high pointer to mid - 1, making our new interval from index 6 to 7.

Step 4: Find the target Our search interval is now very small: [22, 23]. The new middle index is floor((6 + 7) / 2), which is 6. The number at index 6 is 22. Our target, 23, is greater than 22. We update low to mid + 1, which is 7. Now, both low and high are at index 7. The middle is also 7, and the value at index 7 is 23. We found it!

The algorithm stops when either the target is found, or when low becomes greater than high. If low crosses high, it means the element is not in the array.

Efficiency and Requirements

The real power of binary search is its speed. Every time we make a comparison, we cut the search space in half. This makes it incredibly efficient for large datasets. If you have a million items, binary search will take at most 20 comparisons to find what you're looking for. A linear search, checking one by one, could take up to a million comparisons.

This efficiency is described using Big O notation. The time complexity of binary search is $O(\log n)$ , where $n$ is the number of elements in the array. This logarithmic growth is very slow, which is exactly what we want for an algorithm's runtime. The space complexity is $O(1)$ , because it uses a constant amount of extra memory regardless of the array's size—just a few variables to store low, high, and mid.

Algorithm	Time Complexity (Worst Case)	Space Complexity
Linear Search	$O(n)$	$O(1)$
Binary Search	$O(\log n)$	$O(1)$

However, this speed comes with a critical precondition: the array must be sorted. If the data isn't sorted, the core logic of eliminating half the data at each step falls apart. Trying to run binary search on an unsorted array will produce incorrect results or fail to find elements that are actually present.

Binary search can only be applied to a problem if and only if the Problem is monotonic in nature.

The Algorithm in Pseudocode

Looking at the logic in a more formal way helps solidify the concept. Here is the iterative binary search algorithm in pseudocode, which is a simplified, language-agnostic way to describe the steps.

function binary_search(array, target):
  // Set the initial low and high pointers
  low = 0
  high = length(array) - 1

  // Loop as long as the search space is valid
  while low <= high:
    // Calculate the middle index
    mid = floor((low + high) / 2)

    // Get the value at the middle index
    guess = array[mid]

    // Check if the guess is the target
    if guess == target:
      return mid // Found it! Return the index.

    // If guess is too high, search the left half
    if guess > target:
      high = mid - 1
    // If guess is too low, search the right half
    else:
      low = mid + 1

  // If the loop finishes, the target was not in the array
  return -1

This pseudocode follows the exact steps from our example. It initializes the boundaries, then enters a loop that continues as long as the search space is valid (low <= high). Inside the loop, it finds the midpoint, checks the value there, and adjusts the boundaries accordingly. If the target is found, its index is returned. If the loop completes without finding the target, it returns -1 to indicate that the value is not present.

Quiz Questions 1/5

What is the single most critical prerequisite for an array before a binary search can be performed on it?

Quiz Questions 2/5

Given the sorted array [4, 7, 10, 13, 16, 19, 22, 23, 26, 31, 35, 42] and a search for the number 13, what will the search interval be after the first comparison?

Binary search is a foundational algorithm in computer science. Its efficiency makes it a go-to choice for searching in large, sorted datasets, from databases to autocompletion features.

Reverse Binary Search