If your lookup array is sorted ascending / alphabetically, should you ALWAYS be using a Binary (vs Linear) search?

[d0rian]

I'm sitting here dumbfounded at the idea that I might have been doing things the dumb/slow way for 10 years. I've always used the MATCH function with 0 (exact match) as the 3rd (match_type) variable, e.g.
MATCH(lookup_value, lookup_array, 0).

Not sure why, that's just how I was taught. But I've recently learned about Binary vs Linear search, specifically how much faster the former is for large data sets, but with the one important stipulation being that the lookup_array must be sorted in ascending (or A-Z) order or the lookup may not return the correct value.

The speed difference is striking (my lookup arrays are often 20,000 to 100,000 rows long). So much so that it has me wondering whether I should be using a Binary search 100% of the time, even when it means adding the extra step of sorting the lookup_array ascending/alphabetical. I found this page that seems to suggest/test that exact theory (and seems to advocate doing exactly that.)

- Is that more or less correct?
- Are there any pitfalls to doing it this way?
- My lookup array values sometimes don't start in Row 1...e.g. there might be 4 empty (or null > "") cells before my lookup array values begin in A5 for example. Could that compromise this process? Are empty/null-value cells counted as "high" or "low" values for the purposes of ascending/alphabetical sort order?

 

[Sulprobil]

If you only run one LOOKUP then the initial sort plus the LOOKUP will be costlier.
If you run more LOOKUPs, then at some point it will be better to sort first.
Which means: you will know because you know the number of records and the number of iterations.

 

[jasonb75]

Without seeing your sheet layout, I would suggest trying something on the lines of

=INDEX(result range,MATCH(criteria, match range, --(INDEX(match range,MATCH(criteria, match range))= criteria)))

which will compare a binary match result to the criteria to see if it is an exact match, if it is then it will return the result based on that, if it is not an exact match then it will use an linear match instead.

Using this method means that the data doesn't need to be sorted, although depending on the order of the data it may not be any faster than what you are using.