Understanding Binary Search in Kotlin

Welcome to today's lesson! We're diving into Binary Search, a clever technique for locating specific elements within a sorted list. We can find the targeted item by repeatedly dividing the search interval in half. It's akin to flipping through a dictionary — instead of going page by page, you'd start in the middle, then narrow down the section in half until you find your desired word.

Binary Search begins at the midpoint of a sorted list, halving the search area at each step until it locates the target.

Let's search for the number 8 in a sorted list: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. This list has 10 elements with indices 0 to 9.

To find the midpoint: mid = start + (end - start) / 2 = 0 + (9 - 0) / 2 = 4. The element at index 4 is 5. With an even number of elements, integer division gives us the lower middle element.

Since 8 > 5, we search the right half (indices 5 to 9). The new midpoint is index 7, which contains 8 — target found!

This process of repeatedly halving the search space makes Binary Search efficient, eliminating approximately half of the remaining elements with each comparison.

Let's see how Binary Search can be implemented in Kotlin, taking a recursive approach. This process involves a function calling itself — with a base case in place to prevent infinite loops — and a recursive case to solve smaller parts of the problem.

fun binarySearch(arr: IntArray, start: Int, end: Int, target: Int): Int {
    if (start > end) return -1 // Base case
    val mid = start + (end - start) / 2 // Find the midpoint
    return when {
        arr[mid] == target -> mid  // Target found
        arr[mid] > target -> binarySearch(arr, start, mid - 1, target)  // Search the left half
        else -> binarySearch(arr, mid + 1, end, target)  // Search the right half
    }
}

Within this code, the base case is defined first. If the start index is greater than the end index, it indicates the search area is exhausted, resulting in a -1 return. The code then locates the midpoint. If the midpoint equals our target, it's returned. Depending on whether the target is less or more than the midpoint, the search continues within the left or right half, respectively.