The binary search option in Match is not really well advertised in the MS Excel documentation site, so here’s the run down on how to use it.

Binary search are used on sorted lists and are pretty fast.

How binary search works: Binary Vs Linear Search Through Animated Gifs

MATCH (value, array, [match_type] )

If match-type is set to 0, the search will be linear and find an exact match.

If it’s set to 1, binary search will find the largest value that is less than or equal to the search-value. This requires the list have to be sorted in ascending order and when the match is found it needs to be compared with the search value to see if it’s an exact match.

Let’s say in sheet ‘*numbers’ *there are 1 000 000 numbers. In sheet ‘*subset’ *there are 101000 numbers. We want a macro that iterate all numbers in ‘*subset’ to* see if there’s a match in the ‘*number’ *list.

Speed comparison:

matchTest1 – Match: linear search: 704 sec = 11:44 min

matchTest2 – Match: binary search: 3 sec

Option Explicit Public StartTime As Double Public SecondsElapsed As Double Sub runtime(b As Boolean) If b Then Debug.Print "runtime started..." StartTime = Timer Else SecondsElapsed = Round(Timer - StartTime, 4) Debug.Print "Time: " & SecondsElapsed MsgBox "This code ran successfully in " & SecondsElapsed & " seconds", vbInformation End If End Sub Sub matchTest1() ' search linear. Application.ScreenUpdating = False Call runtime(True) Dim ws1 As Worksheet Dim ws2 As Worksheet Dim i As Long Dim hit As Variant Set ws1 = ThisWorkbook.Sheets("numbers") Set ws2 = ThisWorkbook.Sheets("subset") For i = 2 To 101000 hit = Application.Match(ws2.Cells(i, 1), ws1.Range("A1:A1000000"), 0) If Not IsError(hit) Then ws2.Cells(i, 2) = "OK" Else ws2.Cells(i, 2) = "Not found" End If Next Application.ScreenUpdating = True Call runtime(False) End SubSub matchTest2() ' binary search.Application.ScreenUpdating = False Call runtime(True) Dim ws1 As Worksheet Dim ws2 As Worksheet Dim i As Long Dim hit As Variant Set ws1 = ThisWorkbook.Sheets("numbers") Set ws2 = ThisWorkbook.Sheets("subset")' sort listws1.Columns("A").Sort key1:=ws1.Range("A1"), order1:=xlAscending, Header:=xlNo For i = 2 To 101000 hit = Application.Match(ws2.Cells(i, 1), ws1.Range("A1:A1000000"), 1) If Not IsError(hit) Then If ws2.Cells(i, 1) = ws1.Cells(hit, 1) Then 'exact match ws2.Cells(i, 2) = "OK" Else ws2.Cells(i, 2) = "Not exact match" End If Else ws2.Cells(i, 2) = "Not found" End If Next Application.ScreenUpdating = True Call runtime(False) End Sub

Ordinary match are fast enough in most situations, but for huge data sets binary will be worth the effort.

About time comparison, a single linear search for ** n** rows will have worst-case performance O(

*). Binary search in comparison have O(log*

**n***).*

**n**Tip: To return the value found and not the row number, use Application.vlookup, as it has a similar binary search option.