Binary Search Algorithm: Step-by-Step Explanation and Visualization

In the previous article, we introduced binary search and explained why it’s such an efficient searching algorithm. Now, let’s dive deeper into how the binary search algorithm works, step by step. We’ll also use visualizations to make the process even clearer. By the end of this article, you’ll have a solid understanding of the steps in binary search algorithm and be ready to implement it yourself.

Related article: Introduction to binary search for beginners.

Walkthrough of Binary Search Algorithm

Let’s walk through the binary search algorithm step by step, using a simple example of searching for a number in a sorted list. Suppose we have this sorted list of numbers shown below:

2
2
4
4
6
6
8
8
10
10
12
12
14
14
16
16
18
18
20
20
List of Numbers in Ascending Order
List of Numbers in Ascending OrderText is not SVG - cannot display
We need to find out if the number “14” is present in the list. To a computer program performing the search, the number could potentially be at any position in the array. Let’s highlight all possible locations where the target number might be found in green. Below is how the array looks like to the binary search algorithm before the search.

List of Numbers in Ascending Order
List of Numbers in Ascending OrderText is not SVG - cannot display

In the above visualization, the green area represents the current search area, which initially spans the entire array. The target element could be present anywhere in the search space. As we progress through the binary search algorithm, we’ll see how the binary search algorithm reduces the search area by half with each step.

Below is how the binary search algorithm works:

  1. Viewing the Center Element: The binary search begins by looking at the middle element of the current search area highlighted in green. In this case, the center element is 10.
10
10Text is not SVG - cannot display
  1. Comparing with Target: We compare the center element (10) with our target (14). Since the target element (14) is greater than the mid element (10), and the array is in ascending order, we can be sure that all the elements to the left of “10” (2, 4, 6, 8) will be less than our target number. Therefore, we can ignore the left half of the current search range.
2
2
4
4
6
6
8
8
10
10Text is not SVG - cannot display
  1. Reducing the Search Area: The search area is now reduced. The area highlighted in red shows the portion we no longer need to search, effectively cutting our search space in half.
2
2
4
4
6
6
8
8
10
10Text is not SVG - cannot display
  1. New Center Element: In our new, smaller search space contains 5 elements, we again look at the center element. This time, it’s 16.
16
16Text is not SVG - cannot display
  1. Comparing Again: We compare the center element (16) with our target number (14). Since the target number (14) is less than the center element (16), and the array is in ascending order, we can be sure that all elements to the right of 16 will be greater than our target. So, we can ignore the right portion of our current search space.
16
16
18
18
20
20Text is not SVG - cannot display
  1. Further Reducing Search Area: Our search area is reduced even further. We now need to search only 2 places for the target number.
2
2
4
4
6
6
8
8
9
9
16
16
18
18
20
20Text is not SVG - cannot display
  1. Comparing again: In this small search space, the middle element is (12). We compare it with our target number (14). Since the target number (14) is greater than the center element (12), and the array is in ascending order, we can be sure that all the elements to the left of (12) will be less than our target. Therefore, we can ignore the left half of the array from the number (12).
12
12
2
2
4
4
6
6
8
8
10
10
16
16
18
18
20
20Text is not SVG - cannot display
  1. Further Reducing Search Area: Our search area is reduced even further. Our search space now contains only one element.
2
2
4
4
6
6
8
8
10
10
16
16
18
18
20
20
12
12Text is not SVG - cannot display
  1. Final Comparison: We look up the only element present in the search space and compare it with our target (14) and find that they’re equal. This means we’ve found our target!
14
14
2
2
4
4
6
6
8
8
10
10
16
16
18
18
20
20
12
12Text is not SVG - cannot display

Steps in the Binary Search Algorithm

Below are the detailed steps in the binary search algorithm:

  1. Start with a Sorted List: Binary search only works on sorted lists (e.g., list numbers in ascending or descending order, list of names in alphabetical order etc). Ensure your data is sorted before applying binary search.

  2. Define the Search Range: Initially, the search range includes the entire list.

  3. Find the Middle Element:

    • Calculate the middle index of the current search range.
    • Identify the element at this middle index.

  4. Compare with the Target:

    • If the middle element equals the target, congratulations! You’ve found the number you are searching for.
    • If the middle element is greater than the target:
      • The target, if present, must be in the left half of the current range.
      • Update your search range to exclude the right half.
      • Assuming that the list contains numbers in ascending order. If the list contains numbers in descending order, left half should be excluded.
    • If the middle element is less than the target:
      • The target, if present, must be in the right half of the current range.
      • Update your search range to exclude the left half.
      • Assuming that the list contains numbers in ascending order. If the list contains numbers in descending order, right half should be excluded.

  5. Repeat or Conclude:

    • If you’ve found the target, end the search.
    • If the search range has been narrowed down to zero elements, the target is not in the list.
    • Otherwise, go back to step 3 with the updated search range.

Wrapping Up

In our next article, “Binary Search Algorithm: Pseudocode and Explanation” we’ll delve deeper into the programmatic implementation, exploring concepts like high, mid, and low pointers.