Adit Cookbook Pages

Binary Chop

A binary chop is a technique for locating an item in a list quickly and with a consistent and predictable elapsed time.

Suppose you have an array of 100, sorted unique values. If you want to search this array for a particular value then you could just loop through the array until you find the value you want. If you are lucky, and the value is at the beginning of the array, then you will find it quickly but often the value will be towards the end of the serach - at least 50% of the time after half way. Now suppose you could always find the value after accessing no more than 7 elements of the array.

Now increase the array size to 1,000 elements - you just need to access 10 elements to locate your target. 10,000 elements and the maximum is just 14, 100,000 elements and it is no more than 17. Fast, scaleable and consistent - your users will love it. Even if you have to throw in a quick sort at some stage to get things in order you are on to a winner when you retrieve your third value and your program will continue to perform consistently and quickly.

How does it work - well the technique is to get the element at the middle of the array. If it is your value then the algorithm stops. If it is more than your value then you go and look at the element half way between the beginning of the array and the half way point. If it is less, then you check the value half way between the mid point and the end of the array. If you continue dividing the array up in this way you will quickly home in on and locate the required value. What if the value is not in the array at all - well you do need to consider that possibility as the code below shows?

This code fragment will try to deal with a fairly difficult search so that it covers most possible problems - you may well be able to simplify things a bit but it is always a good idea to allow for things going wrong.

The scenario is an array of user defined types. These are pretty simple, with two string values - one is going to be the search “key” and the other is going to be the required value. You could get the function below to return a) the element number of the required value, b) the required value itself or c) a boolean to say if the value is in the array. I have gone for the first option but the changes required for the alternatives are trivial. Returning the element number makes it easy for me to signal back to the calling routine that a specific value has not been found.

Public Type demBC
   keyValue as String * 10
   targetValue as String * 50
End Type
Public BCArray() as demBC

Public Function BinaryChop(SearchValue as String) as Long
   Dim StopPoint As Long, LowPoint As Long, HighPoint As Long
   Dim ChopCount As Long, ChopPoint As Long
   Dim ElemCnt as Long
   Dim Check1 As String, Check2 As String
   Const ValueNotFound = -32767

   ArrayStart = LBound(BCArray())
   ArrayEnd = UBound(BCARRAY())
   If LBound(BCArray()) < 0 then
       ElemCnt = Abs(LBound(BCArray())) + Abs(UBound(BCArray())) + 1
   Else
       ElemCnt = UBound(BCArray()) - LBound(BCArray()) + 1
   End If
   StopPoint = 1
   Do Until 2 ^ StopPoint >= ElemCnt ‘work out the maximum number of elements
       StopPoint = StopPoint + 1        ‘that need to be read to find the value
   Loop
   StopPoint = StopPoint + 1
   LowPoint = LBound(BCArray())
   HighPoint = UBound(BCArray())
   ChopPoint = ((HighPoint - LowPoint) / 2) + LowPoint
   Check1 = Right$(String$(10, “0”) & UCase$(SearchValue), 10)
   ‘We may have to deal with the problem of variable character counts so it can be a
   ‘good idea to pad the strings with leading characters of a low ASCII value
   ‘Plus this search is case insensitive - hence the UCase$() function
   ‘If you need case sensitivity - take it out
   Check2 = Trim$(BCArray(ChopPoint).keyvalue)
   Check2 = Right$(String$(10, “0”) & Ucase$(Check2), 10)
   Do Until Check1 = Check2 Or ChopCount >= StopPoint
       If Check2 < Check1 Then
           LowPoint = ChopPoint
       Else
           HighPoint = ChopPoint
       End If
       ChopCount = ChopCount + 1
       ChopPoint = (HighPoint - LowPoint) / 2 + LowPoint
       Check2 = Trim$(BCArray(ChopPoint).keyvalue)
       Check2 = Right$(String$(10, “0”) & Ucase$(Check2), 10)
   Loop
   If Check1 = Check2 then
       BinaryChop = ChopPoint
   Else
       BinaryChop = ValueNotFound
   End If
End Function

Well this could be improved and/or simplified in many cases depending upon the data being searched and the nature of the array. The function could also be written as a general purpose tool with the array to be searched being passed as well as the search value - well if we ever see a truly object oriented VB to implement it in.