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:

func binarySearch<Element: Comparable>(array: [Element], key: Element) -> Int? {
    var minIndex = 0
    var maxIndex = array.count - 1
    while minIndex <= maxIndex {
        let midIndex = (minIndex + maxIndex) / 2
        if array[midIndex] < key {
            minIndex = midIndex + 1
        } else if array[midIndex] > key {
            maxIndex = midIndex - 1
        } else {
            return midIndex
        }
    }
    return nil
}

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

func binarySearch<Element>(array: [Element], key: Element, comparator: (Element, Element) -> Int) -> Int? {
    var minIndex = 0
    var maxIndex = array.count - 1
    while minIndex <= maxIndex {
        let midIndex = (minIndex + maxIndex) / 2
        let comparison = comparator(array[midIndex], key)
        if comparison > 0 {
            minIndex = midIndex + 1
        } else if comparison < 0 {
            maxIndex = midIndex - 1
        } else {
            return midIndex
        }
    }
    return nil
}

func comparator<Element: Comparable>(element: Element, key: Element) -> Int {
    if element < key {
        return 1
    } else if element > key {
        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:

func binarySearch(arrayCount: Int, tester: (Int) -> Int) -> Int? {
    var minIndex = 0
    var maxIndex = arrayCount - 1
    while minIndex <= maxIndex {
        let midIndex = (minIndex + maxIndex) / 2
        let comparison = tester(midIndex)
        if comparison > 0 {
            minIndex = midIndex + 1
        } else if comparison < 0 {
            maxIndex = midIndex - 1
        } else {
            return midIndex
        }
    }
    return nil
}

func tester(index: Int) -> Int {
    if array[index] < key {
        return 1
    } else if array[index] > key {
        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:

func tester(index: Int) -> Int {
    if array[index] < key {
        return 1
    } else if array[index] > key {
        return -1
    } else if index == 0 || array[index - 1] != key {
        return 0
    } else {
        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.