# Index based binary search

^{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.