Binary search lookups

The binary search algorithm is designed for fast searching. To use this search mode, you need to have a sorted array.

If you are working with Excel, you can use the binary search option to set the 6th (search mode) argument of the XLOOKUP function to 2 or -2.

This guide will show you how the binary search works in different lookup values.

The binary search uses a repeat-until cycle and slices the array into two equal parts until the narrowed array contains the lookup value. In the example below, you can see the differences between the two methods.

Let us see an average case; our lookup value = 37, and we use a sorted array. A Sequential (linear) search uses 11 steps to find the lookup value in the sorted array. On the other hand, binary search tries to look up the same value and uses only three steps.

A picture is worth a thousand words, so take a closer look at how it works:

binary search excel lookups

Source

The following example shows the best case.

The linear search method tries to find the lookup value (=23) in the sorted array, and 9 steps are necessary! On the other hand, binary search slices the array into two equal parts and gets the lookup value using a single step.

Right, it was a lucky pick, but it can happen.

Now, let us see the worst case.

In the example, the lookup value is the first element of the array. A binary search starts to divide the array. The algorithm examines the 8th record first (23), then the 3rd record (7), and so on. In this case, four steps are necessary to find the matching record. Linear search returns with the lookup value in a single step.

worst case

Search Speed comparison in Excel

For testing purposes, we’ll run a speed test:

Configuration:

  • CPU: AMD Ryzen 3700x 8 core, 16 thread / 3.6 GHz
  • RAM: 32GB DDR4
  • OS: Windows 10 Pro
  • Office: Microsoft 365 Apps for enterprise

The lookup array contains 1M records, and we find 100K lookup values. Huge numbers!

  • Setup 1: sorted array, linear search
  • Setup 2: sorted array, binary search

Result:

test result

Are there any differences between Excel lookup methods? Yes, but not significant. The difference is almost unviewable if you work on a strong enough workstation.

Many thanks to Tushar Mehta for the Visual Basic source code.

Excel Functions with binary search options

In Excel, there are some functions with binary search support:

  • XMATCH
  • LOOKUP
  • HLOOKUP
  • VLOOKUP
  • MATCH

Final Words

If you are working on an array that contains unsorted elements, it is not worth using binary search. The median value of the list is located anywhere! For example, when the array (list) has split into two parts, the element you were searching for can be outside the sample.

Istvan Vozar

Istvan is the co-founder of Visual Analytics. He helps people reach the top in Excel.