What is binary search? VLOOKUP is still a great option

By Matthew Herbert on February 15, 2023

You’ve probably seen a post similar to the following: stop using VLOOKUP and use XLOOKUP instead! I shake my head when I see that because most individuals don’t know how these functions truly work. Don’t get me wrong, XLOOKUP is a great function; VLOOKUP is too. Have you considered the amount of CPU time it takes for these calculations to run? If not, then you’re likely slowing your spreadsheet down and over taxing your CPU. The default search type for VLOOKUP is binary (range_lookup = True), and the default search type for XLOOKUP is first-to-last (search_mode = 1).

XLOOKUP also has binary search as an option. Conveniently, IntelliSense helps us see the enumeration values for search_mode:

• 1 search first-to-last
• -1 search last-to-first
• 2 binary search (sorted ascending order)
• -2 binary search (sorted descending order)

{:class=“w-3/5”}

Let’s assume XLOOKUP needs to find the value 18. Search first-to-last will start in the first index position (B2) and compare the value for a match. 10 is not equal to 18. Move to the next index position (C2). 11 is not equal to 18. And so on. Search last-to-first works in the opposite direction – start at L2 and move to B2.

What is binary search?

If we list out some facts about these numbers, then we can quickly discover how to significantly reduce the number of comparisons needed to find the number 18. Fact #1: our data is sorted in ascending order. Fact #2: The smallest number is in the first position. Fact #3: The largest number is in the last position. Fact #4: Each subsequent number is larger than the previous. (Okay, maybe these facts are all the same; you get the point). We don’t need to search every position one by one because we can use the facts to our advantage. Let’s check it out.

A requirement of binary search is that the data is sorted, typically in ascending order. Binary search is also know as a halving algorithm. Begin by moving to the halfway point in the list, or the 6th index position. Is 15 = 18? No. Because 15 is less than 18, there’s no need to compare anything in index positions less than 6 (or values 10 to 14). So, we can move our search to index positions greater than 6. What’s the halfway point within the remaining index positions – 7 to 11? Index position 9. Is 18 = 18? Yes. Binary search found the value 18 in 2 steps. Search first-to-last found the value 18 in 9 steps. That’s a massive improvement in performance.

Why is binary search helpful?

Imagine you have a spreadsheet with 1,000 XLOOKUP functions. Each one of those XLOOKUP functions searches a list containing 15,000 values. Furthermore, let’s assume the list is sorted in ascending order. We let XLOOKUP use search_mode’s default value, or search first-to-last. If our match value is at the bottom of the list, how many comparisons must the XLOOKUP function perform? 15,000. If all our XLOOKUP functions are like this, how many comparisons will Excel perform simply to calculate the result of all 1,000 formulas? That’s right, 1,000 * 15,000, or 15 million! Imagine the performance improvement of using binary search. You would go from 15 million comparisons down to something closer to 1,500 comparisons. That’s roughly 10,000 times faster! Let’s hope those 15 million calculations don’t make you wait. I think we’ve all seen that percent calculation message in the status bar. In this case, you should switch search_mode to binary search (sorted ascending order).

{:class=“w-1/5”}

Because VLOOKUP defaults to approximate match (range_lookup = TRUE), Excel uses binary search by default. Again, your data must be sorted in ascending order. If the data is not sorted, then you’ll get an incorrect result.

If you have a calculation heavy model with thousands of formulas, you should consider how to optimize the calculation performance by leveraging Excel’s built-in features. The formulas are built to work for you.

So, when the topic of XLOOKUP and VLOOKUP comes up, you’ll be able to address the real question: how is your data structured?

If you thought this article was instructive, then enroll in our Excel courses to learn more.