The binary search option in Match is not really well advertised on 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 be used to find the largest value that is less than or equal to the search-value. To use this option 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 1000000 numbers. In sheet subset there are 101000 numbers. We want a macro that iterate all numbers in subset and 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 Sub


Sub matchTest2()
' binear 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 list
ws1.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, linear search thru n rows will have worst-case performance O(n). Binary search in comparison have O(log n).

Tip: To return the value found and not the row number, then Application.vlookup may be a better option, as it have a similar binary search option.

 

 

Advertisements