Microsoft Excel - Use Faster Search Algorithms (Binary vs. Linear/Sequential Searches)

[00:00:03]Hello, I'm Brian with BCTI. In this video, I'm going to discuss Excel's search algorithms. These are the methods of discovery Excel uses when executing functions like VLOOKUP, HLOOKUP, XLOOKUP, etc. The video will be part theoretical and part practical. We'll understand the methods of the different algorithms as well as their strengths and weaknesses. We'll also look at some performance statistics to see how each performs under light and heavy loads.

[00:00:34]Once the theoretical is complete, we'll take a look at Excel's preferred methods of searching and how to alter those methods if we want better control over search performance. So, let's dive right in.

[00:00:47]Be sure to download these files from the link in the video description. I've included PDFs that recap all the information I'm going to cover along with an Excel file that shows various implementations of these search techniques.

[00:01:03]Excel uses at least four distinct search algorithms internally depending on the function and the type of function being performed. Microsoft doesn't document every implementation detail, but from official documentation, observed behavior and performance testing, these are the algorithms Excel is known or very strongly believed to use.

[00:01:26]Two of them linear or sequential search and binary searches. Common functions like VLOOKUP, HLOOKUP, match, XOOKUP, X match, count if, sum if, filter. These use either of these strategies.

[00:01:43]Now, another is a hash lookup. This is for optimized exact matching. This is sort of a behindthescenes strategy Excel appears to use to build temporary lookup structures in some situations. And this is used to accelerate repeated exact match operations.

[00:02:01]Finally, there's indexed lookup. This is where Excel uses row column offsets rather than actual searching uh after the position's already known. So functions like index, choose columns, choose rows, uh take, drop, offset, use these to retrieve data by a position. So this isn't really considered a search, rather a simple retrieval operation.

[00:02:29]Linear searches examine each item one by one until a match is found. In a worst case scenario, if you have a million items in a list, it could take a million tries to locate the item.

[00:02:44]Unlike a linear search, binary searches repeatedly divide sorted lists into halves. Suppose we have a list of 50 sequential numbers. If we are looking for the number 46 which lies between 1 and 50 and the list is sorted in ascending order, we examine the midpoint value of 25 and ask if 46 is above or below 25. If it's below 25, we discard everything above 25. But if it's above 25, we discard everything below 25.

[00:03:12]Next, we divide the list in half again, locate the midpoint, in this case 38, and test to see if 46 lies above or below 38. We discard the non-possible options, cut the remainder in half again, and repeat the test. This process repeats until the value is located.

[00:03:30]As you can see from this table, if we have 1 million entries in a list, we could discover any values location in at most 20 tests. Even if you had one quintilion entries in the list, it would take at most 60 tests to locate a specific value. Here is a result summary of tests I performed when using Excel's VLOOKUP and XLOOKUP functions. When performing a set of 1 million searches and number of times, you can see that binary searches are many orders of magnitude faster than sequential searches. Now, keep in mind that these results are anecdotal and the results will vary depending on machine specifications.

[00:04:12]These tests brought to my attention that the newer XLOOKUP function is actually slower than the older VLOOKUP function when performing sequential searches. My research points to added overhead of XLOOKUP's extended functionality as the reason for this. So don't be so quick to abandon VLOOKUP on large data sets.

[00:04:34]Here is a visual rendition of those values. You can see that as the data size increases, XLOOKUP's performance degrades when executing sequential searches. However, the performance is almost identical to VLOOKUP when performing binary searches.

[00:04:54]But what about approximate match searches? Searches where the value being searched for is not present in the list and you want to retrieve the closest without going over or under. Here's a list of sequential odd numbers between 1 and 99. If we're searching for an even number like 38, we execute the same divide and conquer strategy as before.

[00:05:16]When we are down to the final two surrounding values, we then must decide to either consider the higher or the lower value as a hit.

[00:05:29]Let's now look at how we can take better control of the search methods when using common Excel functions. I have a table here named sales and it has columns like sale number, item names, and prices. And what I'd like to do is I would like to go to this cell here named sale num and type in one of those sale numbers like 1014 and then automatically return the item name and the price. So let's begin with a simple VLOOKUP performing an exact match. So under item name, I'm going to type in equals VL for VLOOKUP.

[00:06:04]We're going to look up whatever I typed here in cell F4, which I named sale num, comma, the table array, that's the entire sales table, comma, and now the return column. Now in normal VLOOKUP, you could only return one thing. So, historically, we'd have to write one VLOOKUP to bring back the item name and another VLOOKUP to bring back the price. But now that we have the new dynamic array engine in Excel, VLOOKUP can bring back more than one thing. If you didn't know this trick, I put out a video some time ago called Unthinkable Lookup Tricks. And I'll put a link in the video description or click the thing up there if it it appears. But check that video out to see this trick along with a whole lot of other really cool lookup tricks that you might not know about. But see now with VLOOKUP we can return multiple columns. You just have to put those column numbers in a set of curly braces. So this creates a list. So curly brace I want to bring back something from column 2 and column 3. Close curly brace.

[00:07:12]And because I want to do an exact match I'm going to use false. Now, here's something else you might not know about.

[00:07:19]You don't actually have to say false.

[00:07:22]You can just say zero because zero means false in Excel. Any other number positive or negative means true, but zero means false. So, in any function where you need a true false response, you can actually replace it with one or zero. So, I'm going to close my parenthesis and hit enter. And I see the non-stick frying pan. Looks like I need to fatten that column up a little bit.

[00:07:46]Probably not that much. But if I were to come up here and type in 1,00, then I'll see Greek yogurt at 254. Now, because this is an exact match, what happens if I put in a sale number that does not exist, like an odd number sale number like 1011.

[00:08:04]Well, then it comes back and it says it can't find it. So, in this case, we might want that. And we could wrap that in an if error and customize to say something like item not found. Uh but we'll look at approximate matches in just a moment. So I'm going to go ahead and put in something that actually exists like 1024. And so now we have cat litter at 2353. That's some very expensive cat litter. Now what if you want to find the closest without going over? So if I did put in something like 1013, instead of giving me a pound NA, it would say, "Hey, that should have landed here between these two rows." So I'm going to give you the closest without going over, which is the permanent markers. So for this one, we need to change the search algorithm from an exact match, which performs a sequential search, to an approximate match, which performs a binary search, the one that does the cutting in half. Now, one of the requirements for the binary search is the data must be sorted in ascending order. Sequential searches do not require any particular sorting of the data. So, we'll go here. We'll perform another VLOOKUP.

[00:09:13]I'm going to look up whatever is in the sale num field, comma, I'm going to look it up in the sales data, comma, and I'm going to return in curly braces the second and the third column, comma. But I want to do an approximate match. So I need to either put the word true here or I can put any number like a one or a two. Doesn't matter. So I'll put close parenthesis. Hit enter. And now I have permanent markers because permanent markers is at 1012 which is just before where 1013 would have landed. So, by switching it to an approximate match, we change the search algorithm from a linear search to a binary search. And remember, binary searches go much faster.

[00:10:01]Even if you're looking for a number that you know is in the data, you could perform a binary search to get that performance boost. Now, let's take a look at the Xookup for doing both of the same. So, I want to perform an exact match lookup using XOOKUP. Now, VLOOKUP defaults to binary searches, the approximate match behavior, and we had to switch it to exact match. XLOOKUP defaults to exact match, and we have to switch it to the binary version. So, in this case, I'm going to perform an XOOKUP. I'm going to look up the sale number, comma, but this time I need to find it only in the sale numbers field, the sale numbers column which I have named sale numbers, comma. And then I want to return information from the item names or the prices or both. Now I've named both of those item names and prices. So what I can do here is I can say item names and then colon prices. So this will get me everything from item names through prices. Again I I can perform two searches in one. Since I'm trying to perform an exact match, which is XLOOKUP's default behavior, I can stop right here. So I'll just go ahead and hit enter. And it says I didn't find it because remember it's looking for the exact match of 1013.

[00:11:24]So if I came up here and changed this to say 1020, I would find breakfast cereal at $16.

[00:11:30]So this is performing the sequential search, the linear search, looking at each item one at a time. Now breakfast cereal happens to be at the beginning of the list, so it returns it very quickly.

[00:11:40]But what if breakfast cereal was a million rows down in this table? This could take much longer, especially for performing hundreds or thousands of these at a time. So, let's perform the exact same thing, but switch it into the binary search mode. Even though it's an exact match, I'm still going to use binary searches. So, here we're going to do an XLOOKUP. I'm going to look up the sale number, comma, in the sale numbers column, comma, I want to return everything from the item names through the prices, but this time, comma, the fourth argument is the built-in error checking. So, if it doesn't find the item, so if I do type in an odd number and I'm doing an exact match, I'd like to know that I didn't find it. So I could put in something in double quotes like item not found, now the match mode. Notice that XLOOKUP defaults to exact match, which is what I'm going to pick. But you could also put it into approximate match mode. But if you don't find the item, pick the item that is closest to it without going over. Now, that requires list be sorted in ascending order. You can also pick the closest without going under. So in other words, if I don't find it, pick the one that comes right after it. Now, I'm going to go with exact match, comma.

[00:13:04]But here's where I can tell it that I want to perform a binary search. If you pick one of the first two choices, search first to last or last to first, these will perform sequential searches.

[00:13:16]Now, we didn't have to tell it to do that in the previous example because the default is to do first to last. However, if you're searching for things like in a dated a date sorted list and the items you're searching for, you know, will always be closer to the bottom because they're the more recent items, why not do your search from a bottom up perspective? And that way, you can just cut down on the number of searches. Now, in our case, we want to perform a binary search and then you have to tell it whether the data is sorted in ascending or descending order. In our case, it's sorted in ascending order. So, I'm going to choose number two, close parenthesis, and hit enter. And we found breakfast cereal. So, even though we were trying to find the exact item, we didn't perform a sequential search. We performed a binary search. So, I would say we discovered this in this entire list of about 6,000 items in about 12 hits. So, it doesn't matter where 1020 would be in this list, we would still find it in about 12 hits at most. Now, because we were still set to an exact match, if I typed in something like 1021 as the sale number, we didn't find it.

[00:14:26]So, we're going to get that item not found returned error message. Well, let's switch this into approximate match mode and we'll perform the binary search that way and see what we come up with.

[00:14:38]So, going back into the cell, I'm going to go back into editing. And for the match mode, I'm going to take out that zero. And we're going to say, "Hey, go ahead and give me the exact number if you find it, but if you don't find it, give me the one that would have been just before that." So, the exact or closest without going over. So, I'm going to change that to a negative one.

[00:15:00]Now, in terms of the search mode, do I want to search from the top down or the bottom up? This would be for a sequential search. or do I want to perform a binary search and is the data sorted in ascending order or descending order? Now, here's where you could actually override the approximate match binary search and make it perform a sequential search. So, this would actually make things go slower. So, I don't think you'd want to do this. So, we're going to perform a binary search and it's sorted in ascending order. So, that would be a two. We'll go ahead and hit enter. and 1021 is not in the list, but item 1020, breakfast cereal, is the return item. So, this performed a binary search to find it exactly or closest without going over.

[00:15:47]Finally, how would we discover an item that is below the searched item if the searched item is not found? So, in our case, the XLOOKUP is almost exactly the same. So, I'm going to take that previous one. I'm just going to copy it and then go down here and paste it. So, what we're going to do is we're going to back off those last couple arguments.

[00:16:07]So, in this case, we want to find the exact match or the next larger item. So, if you don't find in the list, go one step beyond that and return whatever is there. So, we'll choose a one, and I want to perform a binary search.

[00:16:22]And I have to tell it that my data is sorted in ascending order. So, that's going to be a two. close parenthesis and hit enter. And you can see that 1021 is not in the list. So it brings back 1022, which is the extension cord. Now, what would happen if I went over to this list and I sorted it in descending order?

[00:16:42]Well, the first one, that previous XLOOKUP that says find the closest without going over, assumes that my data is sorted in ascending order, and it fails. But the second one brought back bleach at $16.54.

[00:16:57]The reason for that is it's looking for 1021 and it immediately hit 14868 and said, "Wait a minute. I should have found that by now. It must not be in the list." So, I'll go ahead and bring back the item that would have come after that, which would be 14868.

[00:17:14]Well, we have to go back into the XLOOKUP and go into our search mode and tell it that our data is in descending order. So, we still want to perform a binary search. It's just the date is in descending order. So we'll choose a -2 for that. Go ahead and hit enter. And now we get extension cord which if you look in the original list would have been the one just before the searched for number because the list is in descending order. So if I go back to ascending order and we look at that xookup, we'd have to tell it to make sure we do the binary search in an ascending order list. But whether your list is in ascending or descending order, going back to this one, that exact match or next smaller or next larger can work with either sorted direction.

[00:18:03]So there it is, a brief tutorial on the difference between linear searches and binary searches, the advantages and disadvantages of both, and how to take control over which one you use as opposed to the one Excel wants to use.

[00:18:18]Be sure to download these files from the link in the video description. So you can go through and test all of these things yourself and also take advantage of the PDF files I've included that has a more English descriptive breakdown of all of this information. So let me know your thoughts in the comments.

[00:18:35]Thank you for watching and remember at BCTI the learning never stops.