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.
Differences between Binary search and Linear search
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:
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.
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:
Are there any differences between Excel lookup methods? Yes, but not significant. The difference is almost unviewable if you work on a workstation that is strong enough.
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.
Related Formulas and Resources:
- Find the last match using XLOOKUP
- How to use left lookup in Excel
- Wildcard search
- Case-sensitive lookups using XLOOKUP