LESSON 248 OF 348 · BINARY SEARCH

Binary Search in Kotlin: O(log n) on a Sorted IntArray

Lesson O(log n) Read the full explanation

In this video lesson we will learn about the concept of searching, linear searching and more important - Binary Searching:

Problem:

Given a sorted array of integers nums, use Binary Search to find and return 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(1) extra space.

STEP 1 OF 7

Guided

Ctrl + Enter to check

KOTLIN · BINARY SEARCH

Binary Search in Kotlin, explained

Problem overview

The function find receives a sorted IntArray called nums and an integer value. It returns the index where value sits in nums, or -1 when the value isn't there. The array is sorted in ascending order, and that is the fact the whole solution relies on.

In the example, nums = [1, 2, 4, 5] and value = 4. The value 4 is at index 2, so the answer is 2. Searching the same array for 3 returns -1.

The statement asks for O(log n) time and O(1) extra space.

Approach: halve the search range each time

Linear search checks the elements one by one from the start. It works on any array, but it takes O(n) time, because the value may be at the very end or missing. When the array is sorted you can do much better.

Look at the element in the middle of the range. There are three cases:

It equals value: you found it.
It is smaller than value: because the array is sorted, everything to its left is smaller still, so the value can only be to the right.
It is larger than value: everything to its right is larger too, so the value can only be to the left.

In the last two cases, one comparison throws away half of the remaining elements. Halving repeatedly takes about log₂(n) steps: a million elements need roughly 20 comparisons.

The range is tracked with two indices, left and right, both inclusive. Searching [1, 2, 4, 5] for 4: the range is indices 0 to 3, the middle index is 1, and nums[1] is 2, which is smaller than 4, so the range becomes 2 to 3. The middle is now index 2, and nums[2] is 4, so the function returns 2.

Step by step

Set the bounds. left starts at 0 and right at nums.size - 1, the last valid index. Both are var, because they move inside the loop. Both are inclusive: right points at a real element, not one past it.
Loop while the range has elements. The condition is left <= right. With <=, a range of exactly one element still gets checked, and the loop ends only when left passes right.
Find the middle. middle is left + (right - left) / 2. Integer division rounds down, so the result is always a valid index in the range.
Found it. If nums[middle] == value, return middle immediately.
Too small. If nums[middle] < value, set left = middle + 1. The middle element is already ruled out, so the next range starts after it.
Too big. Otherwise set right = middle - 1, for the same reason.
Not found. When the loop ends, every candidate has been discarded, so return -1.

The solution in Kotlin

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

Kotlin details that matter:

/ on two Int values is integer division, which truncates, so no rounding call is needed. Here the quantity is never negative, so truncating and rounding down agree.
left + (right - left) / 2 gives the same index as (left + right) / 2, but it can't overflow. Int is 32 bits and wraps silently: with left = 2_000_000_000 and right = 2_100_000_000, the sum left + right wraps to a negative number and (left + right) / 2 becomes -97483648. The safer form gives 2050000000. Arrays that large are rare, but the habit costs nothing.
nums.size - 1 is -1 for an empty array. Then left <= right is false from the start, the loop doesn't run, and the function returns -1.
return inside the loop ends the function at once. The final return -1 sits after the loop, and it is reached only when no element matched.
The if/else if/else chain is a statement here. Kotlin's when would work as well, but the chain mirrors the three cases directly.

Complexity

Time is O(log n): each pass of the loop halves the range, so there are at most about log₂(n) + 1 passes. Space is O(1): the function keeps three integers and doesn't build any collection.

Edge cases and common mistakes

Using left < right. The last remaining element is never examined, so a search for the only element of a one-element array fails.
Setting left = middle or right = middle. The middle element was already checked. Keeping it in the range can leave the range unchanged and make the loop run forever.
Searching an unsorted array. Binary search discards halves based on the order. If the array isn't sorted, the answer is meaningless.
Value smaller than everything, or larger than everything. The range shrinks to nothing on one side, and the function returns -1.
Duplicates. If value appears several times, the function returns the index of one of them, not necessarily the first.

Testing

[1, 2, 4, 5] with value = 4 returns 2.
[1, 2, 4, 5] with value = 3 returns -1.
[] with value = 3 returns -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