Binary Search (Code)

In our last blog post we talked about how binary search is able to complete a search in a Logarithmic time frame.  In this post the goal is to show you visually how the code differs between counting one at a time vs doing a binary search.

Code (Kotlin)

// Binary Search 
fun search(array: IntArray, target: Int): Int {
    var low = 0 # lowest starting point
    var high = array.size # highest starting point
    while (low < high) { 
        val mid = (low + high) / 2 # calculate middle
        val value = array[mid] # get value of middle
        if (value == target) { # if target is equal to middle
            return mid # return the index of the target 
        } else if (target > value) { # if target is greater than value 
            low = mid + 1 # set low = mid + 1
        } else {
            high = mid # set high = mid
        }
    }
    return -1 # we didn't find the number in the array
}

var index = search(array=intArrayOf(0,1,2,3,4,5,6,7,8,9), target=5)
if (index >= 0) {
   println("Found target a index $index");
} else {
   println("We did not find the number in the array");
}