Start learning free

LESSON 259 OF 348 · DIVIDE AND CONQUER

Recursive Binary Search in Kotlin: O(log n) Time and Space

Practice Recursive Read the full explanation

Implement a recursive Binary Search algorithm that given a sorted array of integers nums, finds and returns the index of a given value.

If the value doesn't exist in nums, return -1.

Example 1:

Input: nums = [1, 2, 4, 5], value = 4
Output: 2
Explanation: nums[2] is 4

Note:

Your algorithm should run in O(log n) time and use O(log n) extra space.

Hints:

Since our subproblems reduce to searching the value in a subarray, we will write a recursive function binarySearch(nums, left, right) which looks for value in nums[left...right] and returns its index or -1 if not found.

Inside the function, we should compute the middle index mid and compare nums[mid] to value. What should we do if:
  • a[mid] is equal to value?
  • a[mid] is less than value?
  • a[mid] is greater than value?

  • If a[mid] is equal to value, then we found our solution and we should return mid
  • If a[mid] is less than value, we should continue the search in nums[mid + 1...right], e.g. return binarySearch(nums, mid + 1, right)
  • If a[mid] is greater than value, we should continue the search in nums[left...mid - 1], e.g. return binarySearch(nums, left, mid - 1)
When should the function return -1 tho?

At the start of the function, we should treat the base case: left > right. This means we reduced the searching area to an empty subarray, so there is no solution and we should return -1
STEP 1 OF 7
    Ctrl + Enter to check

    KOTLIN · DIVIDE AND CONQUER

    Binary Search in Kotlin, explained

    Problem overview

    The function find receives a sorted IntArray called nums and an Int called value. It returns the index of value in nums, or -1 when the value is absent. The search has to be recursive and run in O(log n) time with O(log n) extra space.

    For nums = [1, 2, 4, 5] and value = 4 the answer is 2, because nums[2] is 4.

    Approach: shrink the range with each call

    Binary search compares the target with the middle element of a range. Because the array is sorted, that single comparison removes half of the range:

    • If the middle element equals value, return its index.
    • If the middle element is smaller than value, the target can only be to the right, so search the range after the middle.
    • If the middle element is larger, the target can only be to the left, so search the range before the middle.

    The recursive version expresses "search a smaller range" as a call to itself. The helper binarySearch(nums, left, right, value) searches only nums[left..right]. The bounds travel as parameters, so each call works on the same array without copying any part of it.

    The base case is an empty range: when left has moved past right, there is nothing left to look at, so the value is not present and the answer is -1.

    Take [1, 2, 4, 5] and value = 4. The first call covers indices 0 to 3, and the middle index is (0 + 3) / 2 = 1, holding 2. That is smaller than 4, so the next call covers indices 2 to 3. Its middle is 2, which holds 4, so it returns 2. Each earlier call returns what the call below it returned, and the 2 comes back to find.

    Step by step

    1. Delegate from find. The function returns binarySearch(nums, 0, nums.size - 1, value), so the first call covers the whole array.
    2. Declare the helper above find with the array, the bounds left and right, and the target. Passing the bounds lets every call narrow the range.
    3. Write the base case. If left > right, return -1. Without it the recursion would continue until the stack overflows.
    4. Compute mid as a val, the index halfway between left and right.
    5. Check for a match. If nums[mid] == value, return mid at once. The next two branches then handle only "too small" and "too big".
    6. Go right when the middle is too small. Return the result of binarySearch(nums, mid + 1, right, value). The return matters: it passes the index found deep in the recursion back up the chain.
    7. Otherwise go left. Return binarySearch(nums, left, mid - 1, value). Using mid - 1 rather than mid drops the element already ruled out; keeping it could repeat the same range forever.

    The solution in Kotlin

    class Solution {
    fun binarySearch(nums: IntArray, left: Int, right: Int, value: Int): Int {
        if (left > right) {
            return -1
        }
        val mid = (left + right) / 2
        if (nums[mid] == value) {
            return mid
        }
        if (nums[mid] < value) {
            return binarySearch(nums, mid + 1, right, value)
        } else {
            return binarySearch(nums, left, mid - 1, value)
        }
    }
    fun find(nums: IntArray, value: Int): Int {
        return binarySearch(nums, 0, nums.size - 1, value)
    }
}

    The Kotlin details worth a closer look:

    • Parameters are read-only. The bounds are never reassigned. Each recursive call receives new values, so no var is needed anywhere in the function.
    • Arrays are references. Passing nums to the recursive call hands over the same array object, so the cost of a call doesn't depend on the array's size.
    • Integer division. (left + right) / 2 drops the fraction, so for non-negative indices it is always a valid index in the range. For huge arrays left + right could overflow an Int; left + (right - left) / 2 is the safe form.
    • Every path returns. The last if/else returns in both branches, so Kotlin accepts the function without a statement after it.
    • No automatic tail-call optimisation. The recursive calls here are the last thing the function does, but the compiler turns them into a loop only if the function is marked tailrec. Without it, each call uses a stack frame. That is the O(log n) space the statement describes.

    Complexity

    Time: O(log n). Each call does constant work and passes on at most half of its range, so there are at most about log2(n) + 1 calls.

    Space: O(log n). The calls are pending on the stack until the answer returns, and the depth is the same logarithmic number. For an array of a million elements that is about 20 frames.

    Edge cases and common mistakes

    • Empty array. The first call has left = 0 and right = -1, which is the base case, so the function returns -1.
    • Value missing. For [1, 2, 4, 5] and value = 3, the range shrinks until left passes right, and the result is -1.
    • First and last elements. The value 1 gives index 0 and 5 gives index 3 in the example array.
    • Base case as left == right. A range of one element still has to be compared. Stopping when left == right would skip it.
    • Forgetting return before the recursive call. The call runs, but its result is discarded, and the compiler complains that the function needs a return.
    • Using mid in both recursive calls. Searching mid to right or left to mid can produce a range that never shrinks, such as a one-element range.
    • Unsorted input. Binary search assumes sorted data. On an unsorted array it can miss values that are present.

    Testing

    • nums = [1, 2, 4, 5], value = 4 gives 2.
    • nums = [1, 2, 4, 5], value = 3 gives -1.
    • nums = [1, 2, 4, 5], value = 1 gives 0.
    • nums = [1, 2, 4, 5], value = 5 gives 3.
    • nums = [], value = 3 gives -1.
    Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free