Binary Search: Lookup Efficiency With MatchType Set to 1

Aladin Akyurek

Aladin Akyurek

MrExcel MVP
Joined
Feb 14, 2002
Messages
85,210
Quoted from: http://www.mrexcel.com/board2/viewtopic.php?t=87050

formula 1:

=VLOOKUP(B14,{"Deluxe Tour",128;"Jungle River Safari",88;"My Generation Tour Adult Only",128;"Power Boat Jeep Rental",295},2,0)

formula 2:

=LOOKUP(B14,{"Deluxe Tour","Jungle River Safari","My Generation Tour Adult Only","Power Boat Jeep Rental";128,88,128,295})

i've often wondered how these two would perform next to each other in like conditions, one syntax to another. any idea aladin?
_________________
Regards,
Zack
Click to expand...

Both formulas use a sorted built-in table. The LOOKUP formula invokes binary search, the VLOOKUP formula linear search as determined by the match-type = 0. Therefore the LOOKUP formula will be faster.

How do VLOOKUP, LOOKUP, INDEX/MATCH perform when all invoke binary search?

Before proceeding further, one thing must be noted. Using binary search formulas with sortedtextrequires caution. To see this, enter in B14 the following:

Voyage au bout de la nuit

The LOOKUP formula happily returns 295, while the VLOOKUP formula with match-type set to 0 errors out.

=VLOOKUP(B14,{"Deluxe Tour",128;"Jungle River Safari",88;"My Generation Tour Adult Only",128;"Power Boat Jeep Rental",295},2,1)

would behave like the LOOKUP formula.

This cautionary note does not apply to the use of BigNum/BigStr as lookup values in formulas which invoke binary search in order to determine last numeric/text values in ranges of interest.

How about performance differences?

What follows compares the following sets of formulas:

[1]

=VLOOKUP(B7,AccList!$F$2:$H$9978,3,1)

=VLOOKUP(B7,AccList!$F$2:$L$9978,7,1)

[2]

=LOOKUP(B7,AccList!$F$2:$F$9978,AccList!$H$2:$H$9978)

=LOOKUP(B7,AccList!$F$2:$F$9978,AccList!$L$2:$L$9978)

[3]

=INDEX(AccList!$H$2:$H$9978,MATCH(B7,AccList!$F$2:$F$9978,1))

=INDEX(AccList!$L$2:$L$9978,MATCH(B7,AccList!$F$2:$F$9978,1))

[4]

=INDEX(AccList!$H$2:$H$9978,H7)

=INDEX(AccList!$L$2:$L$9978,H7)

=MATCH(B7,AccList!$F$2:$F$9978,1)

which is in H7.

As is clear, the lookup table is in AccListF2:L9978. Column F houses text-formatted account-numbers and the table is sorted in ascending order on F.

Each formula is copied to 6255 cells.

The figures are averages of 5 runs.
All With BS MrExcel.xls
ABCDEFGHI
1FastExcelWorkBookProfileVersion2.0Build434
2WorkBookSummary
3CalcTime(Millisec)%MicroSecsRangeTotal
4ConstFormulaReCalcFullCalcVolatile/FormulaMem(K)Mem(K)
5[1]VLOOKUP94,93512,5220.2115.60.2%9.22,0712,136
6[2]LOOKUP94,93512,5220.2109.70.2%8.82,1192,208
7[3]INDEX/MATCH(a)94,93512,5220.2118.20.2%9.42,1952,260
8[4]INDEX/MATCH(b)94,93518,7830.291.90.3%4.92,3192,406
9
FastXL
 

Excel Facts

How to calculate loan payments in Excel?
Use the PMT function: =PMT(5%/12,60,-25000) is for a $25,000 loan, 5% annual interest, 60 month loan.
Sort by date Sort by votes
fairwinds said:
Hi,

How do I interpret no 4, is there one Match formula for each index formula?
Click to expand...

No, just one for both. MATCH determines in H7 the position of B7. INDEX pulls off values from two different columns.
 
Upvote 0
So even if I had one match for each index it should be a little faster than Index / match combination (in one cell)...?
 
Upvote 0
so the INDEX/MATCH combo is slightly bulkier and uses slightly more memory to function. but in the same breath, if you break apart the two functions and use in conjunction with each other from different cells, your memory usage will go up yet re-calc time will inversely go down drastically. am i following this right so far? so from the above example, i would have to conclude that it is sometimes much more effective, if measuring performance standards, to break apart computations which rely on each other, keeping in mind the desired results and route/method used to achieve them. maybe not all the time, but where the occasion presents itself.

or do i need more coffee today :lol:
 
Upvote 0
firefytr said:
so the INDEX/MATCH combo is slightly bulkier and uses slightly more memory to function. but in the same breath, if you break apart the two functions and use in conjunction with each other from different cells, your memory usage will go up yet re-calc time will inversely go down drastically. am i following this right so far? so from the above example, i would have to conclude that it is sometimes much more effective, if measuring performance standards, to break apart computations which rely on each other, keeping in mind the desired results and route/method used to achieve them. maybe not all the time, but where the occasion presents itself.

or do i need more coffee today :lol:
Click to expand...

That's right. That's also why I often suggest a 2-cell approach instead of:

=IF(ISNA(VLOOKUP()),X,VLOOKUP())

The issue is knows as space/time trade off.
 
Upvote 0
Aladin Akyurek said:
That's right. That's also why I often suggest a 2-cell approach instead of:

=IF(ISNA(VLOOKUP()),X,VLOOKUP())

The issue is knows as space/time trade off.
Click to expand...

gotcha. never did like that type of combo anyway. usually becomes quite cumbersome. but nonetheless, your results are interesting and provokes one to examine their judgement call/s on providing 'the right solution' to a question.

btw, thank you very much for taking the time to examine that question. i appreciate it!
 
Upvote 0
fairwinds said:
So even if I had one match for each index it should be a little faster than Index / match combination (in one cell)...?
Click to expand...

Yes. It's better performancewise for example to replace:

=VLOOKUP(LookupVal,$A$2:$D$2000,2,MatchType)

=VLOOKUP(LookupVal,$A$2:$D$2000,3,MatchType)

=VLOOKUP(LookupVal,$A$2:$D$2000,4,MatchType)

or

{=VLOOKUP(LookupVal,$A$2:$D$2000,{2,3,4},MatchType)}

with

X2:

=MATCH(LookupVal,$A$2:$A$2000,MatchType)

=INDEX(B$2:B$2000,$X2)

copied across.
 
Upvote 0
Thanks, Aladin. We have one spreadsheet that has thousands of lookups exactly like that. And it takes a while to re-calculate. It isn't my spreadsheet, but the person has asked about trying to speed it up. I am looking forward to making the substitutions recommended here to see what happens.
 
Upvote 0
You must log in or register to reply here.

Similar threads

Sean15
  • Solved
Rewrite formula so 2nd, 3rd…occurrence of lookup value return blank cell
Replies
6
Views
255
Peter_SSs
Peter_SSs
C
  • Solved
index match excel formula to vba code
Replies
9
Views
369
DanteAmor
DanteAmor
L
  • Question Question
Help with formula to keep leading zero in cell - cant format as date
Replies
4
Views
72
6StringJazzer
6StringJazzer
J
  • Question Question
Index, Match, Large based on two Criteria
Replies
3
Views
115
Fluff
Fluff
J
  • Solved
Lookup formula to determine activity use
Replies
4
Views
179
kvsrinivasamurthy
K

Forum statistics

Threads
1,224,874
Messages
6,181,504
Members
453,048
Latest member
engkinooi

Share this page

We've detected that you are using an adblocker.

We have a great community of people providing Excel help here, but the hosting costs are enormous. You can help keep this site running by allowing ads on MrExcel.com.
Allow Ads at MrExcel

Which adblocker are you using?

Disable AdBlock

Follow these easy steps to disable AdBlock

1)Click on the icon in the browser’s toolbar.
2)Click on the icon in the browser’s toolbar.
2)Click on the "Pause on this site" option.
Go back

Disable AdBlock Plus

Follow these easy steps to disable AdBlock Plus

1)Click on the icon in the browser’s toolbar.
2)Click on the toggle to disable it for "mrexcel.com".
Go back

Disable uBlock Origin

Follow these easy steps to disable uBlock Origin

1)Click on the icon in the browser’s toolbar.
2)Click on the "Power" button.
3)Click on the "Refresh" button.
Go back

Disable uBlock

Follow these easy steps to disable uBlock

1)Click on the icon in the browser’s toolbar.
2)Click on the "Power" button.
3)Click on the "Refresh" button.
Go back
Back
Top