UtterAccess HomeUtterAccess Wiki

Welcome Guest ( Log In | Register )

Custom Search
Edit Discussion
> BLOOKUP a Binary Lookup For Excel    
BLOOKUP a Binary Lookup For Excel

Contents

Acknowledgement

The main part of this code came from http://www.developershandbook.com/Downloads/1951c04.pdf. I changed very little of it.

BLOOKUP a Binary Search for Excel

A binary search is also known as a half-interval search. It works on a sorted list and can cut down the time it takes to find an item immensely.

Basically, it works by recursively cutting a range in half. For example if you are looking for a number in a list of 1024 numbers, first pick the 512nd record (half way) and then determine if the number associated with that record is either equal to (in which case stop) or greater than or less than the number sought. If the number found is less than or greater than the desired number, throw away the other half of the list and pick the midpoint of the remaining list and so on.

In the worst case with 1024 items, you have to do this 9 times. This is much more efficient than starting at the top and going through every record until you find what you are looking for. A top to bottom search is superior only if what you are looking for is in the first 9 records. There will be some loss of efficiency because there is more decision making to do in a binary search (Is the number less than, equal to or greater than what you are looking for? What is the midpoint of the surviving range?) as compared to “move to next record.” However the “divide and conquer” approach overwhelms this small penalty.

The maximum number of steps for a binary search is given by log2 N. You mathematicians know what that means, but what it says in layman’s terms is the larger N (the number of records to search through) is, the more efficient a binary search is when compared to a top-to-bottom search.

As a basis of comparison, the table below shows the number of steps for various N and the ratio (N/steps).

image: Table.jpg

When to use a binary search?

BLOOKUP is based on a binary search and requires that the data be sorted ascending. Normally VLOOKUP is good enough. If you have a reasonable number of records to search through, use VLOOKUP. However if you are looking up against hundreds of thousands of records BLOOKUP may do it faster. You will have to make a determination as to the trade off between sorting the data so BLOOKUP can work, or just plowing through with VLOOKUP.

Syntax

BLOOKUP has 4 arguments. The first three are similar to VLOOKUP. The fourth is an enhancement.

The syntax for BLOOKUP is: BLOOKUP (Search_for, Search_in, Column_to_Return, [Search_position])

  • Search_for is the value you wish to search for.
  • Search_in is the array that contains the data to search.
  • Column_to_return is the column that contains the data you want to see
  • Search_position is an optional argument. It is the column in the Search_in array on which to look up. By default it is 1 meaning that BLOOKUP works like VLOOKUP. However, you can tell BLOOKUP to look at the 3rd column and return the data found in the 2nd column. The search position is the column on which the data must be sorted.

The function returns the value if it finds it, otherwise it returns #N/A.

Code

CODE

Option Explicit
Option Base 1

' BLOOKUP (Lookup Value, Lookup Range, Column to Return, Column to look up on)
' Column to look up on is optional with a default value of 1

Function BLOOKUP(MyValue As Variant, MyRange As Range, BCol As Long, Optional BLook As Long = 1)
Dim FoundRow As Long

FoundRow = BSearch(MyRange, MyValue, BLook)

If FoundRow = -1 Then
   BLOOKUP = CVErr(xlErrNA)
Else
   BLOOKUP = MyRange(FoundRow, BCol)
End If

End Function

Function BSearch(MyRange As Range, varSought As Variant, BLook As Long) As Long
Dim intLower As Integer
Dim intMiddle As Integer
Dim intUpper As Integer

Application.Volatile

intLower = 1
intUpper = MyRange.Rows.Count

Do While intLower < intUpper
' Increase lower and decrease upper boundary,
' keeping varSought in range, if it’s there at all.
intMiddle = (intLower + intUpper) \ 2

If varSought > MyRange(intMiddle, BLook) Then
   intLower = intMiddle + 1
Else
   intUpper = intMiddle
End If

Loop
If MyRange(intLower, BLook) = varSought Then
   BSearch = intLower
Else
   BSearch = -1
End If

End Function
Edit Discussion
Custom Search
Thank you for your support!
This page has been accessed 4,773 times.  This page was last modified 16:42, 4 September 2014 by dflak. Contributions by Jack Leach  Disclaimers