Index based binary search

26^th January 2020

There are many algorithms that work with arrays have some kind of element comparison in them. Here’s a lightly edited version of the Binary search algorithm from Wikipedia:

function BinarySearch(Array, ArrayLength, Key) is
    minIndex := 0
    maxIndex := ArrayLength − 1
    while minIndex ≤ maxIndex do
        midIndex := floor((minIndex + maxIndex) / 2)
        if A[midIndex] < Key then
            minIndex := middleIndex + 1
        else if A[midIndex] > Key then
            maxIndex := midIndex - 1
        else:
            return middleIndex
    return Unsuccessful

Some implementations abstract this comparison (A[midIndex] < Key above) into an external function or closure:

function BinarySearch(Array, ArrayLength, Key, Comparator) is
    minIndex := 0
    maxIndex := ArrayLength − 1
    while minIndex ≤ maxIndex do
        midIndex := floor((minIndex + maxIndex) / 2)
        comparison = Comparator(A[midIndex], Key)
        if comparison > 0 then
            minIndex := middleIndex + 1
        else if comparison < 0 then
            maxIndex := midIndex - 1
        else:
            return middleIndex
    return Unsuccessful

function Comparator(ElementA, ElementB) is
	  if ElementA < ElementB then
        return 1
    else if ElementA > ElementB then 
        return -1
    else
      return 0

Notice that in order to do the comparison we need the array itself and the key, which we supplied to the algorithm. The only the thing supplied by the algorthirm was midIndex.

I think we can abstract this far more than normally seen by just passing midIndex to the external function:

function BinarySearch(ArrayLength, Tester) is
    minIndex := 0
    maxIndex := ArrayLength − 1
    while minIndex ≤ maxIndex do
        midIndex := floor((minIndex + maxIndex) / 2)
        comparison = Tester(midIndex)
        if comparison > 0 then
            minIndex := middleIndex + 1
        else if comparison < 0 then
            maxIndex := midIndex - 1
        else:
            return
    return

function Tester(ElementIndex) is
	  if Array[ElementIndex] < Key then
        return 1
    else if Array[ElementIndex] > Key then 
        return -1
    else
      return 0

Worth noting here that we don’t need to return anything from algorithm as we can handle the success scenario in the external function.

Procedure for finding the left most element

Now we have full abstracted the testing our of the algorithm, and vice versa we can do some interesting things. For example, here’s the tester that will give the left most matching element:

function Tester(ElementIndex) is
	  if Array[ElementIndex] < Key then
        return 1
    else if Array[ElementIndex] > Key then 
        return -1
    else if ElementIndex = 0 or Array[ElementIndex - 1] ≠ Key
        return 0
    else if 
        return -1
        

This only works because we can perform a test on any element from the tester, not just on the element given.

Even with the most common, often builtin, functions it’s worth taking the time to consider what is actually going on, and to see if it can be played with or improved upon.