BLOOKUP a Binary Lookup For Excel
[edit] AcknowledgementThe main part of this code came from http://www.developershandbook.com/Downloads/1951c04.pdf. I changed very little of it. [edit] BLOOKUP a Binary Search for ExcelA binary search is also known as a halfinterval 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 toptobottom search. As a basis of comparison, the table below shows the number of steps for various N and the ratio (N/steps). [edit] 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. [edit] SyntaxBLOOKUP 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])
The function returns the value if it finds it, otherwise it returns #N/A. [edit] CodeCODE 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

Custom Search

This page has been accessed 8,273 times. This page was last modified 16:42, 4 September 2014 by dflak. Contributions by Jack Leach Disclaimers 