Kotlin Program for Binary Search with Example

A Kotlin program for binary search uses a while loop to repeatedly divide the sorted array and compare the middle element with the target, like fun binarySearch(arr: IntArray, target: Int): Int which returns the index or -1 if not found.

Examples

Input[1, 3, 5, 7, 9], target=5

Output2

Input[2, 4, 6, 8, 10], target=7

Output-1

Input[10], target=10

Output0

How to Think About It

To do a binary search, first check the middle element of the sorted list. If it matches the target, return its position. If the target is smaller, repeat the search on the left half; if larger, on the right half. Keep doing this until you find the target or the search space is empty.

Algorithm

1

Start with two pointers: low at the start, high at the end of the array.

2

While low is less than or equal to high:

3

Calculate middle index as (low + high) / 2.

4

If the middle element equals the target, return the middle index.

5

If the middle element is less than the target, move low to middle + 1.

6

Else, move high to middle - 1.

7

If the target is not found, return -1.

Code

kotlin

fun binarySearch(arr: IntArray, target: Int): Int {
    var low = 0
    var high = arr.size - 1
    while (low <= high) {
        val mid = (low + high) / 2
        when {
            arr[mid] == target -> return mid
            arr[mid] < target -> low = mid + 1
            else -> high = mid - 1
        }
    }
    return -1
}

fun main() {
    val arr = intArrayOf(1, 3, 5, 7, 9)
    val target = 5
    val result = binarySearch(arr, target)
    println(result)
}

Output

2

Dry Run

Let's trace the search for target 5 in array [1, 3, 5, 7, 9].

1

Initialize pointers

low = 0, high = 4 (array indices)

2

Calculate mid

mid = (0 + 4) / 2 = 2

3

Compare mid element

arr[2] = 5 equals target 5, return 2

low	high	mid	arr[mid]	comparison
0	4	2	5	5 == 5, found target

Why This Works

Step 1: Divide and conquer

The code splits the array into halves by calculating the middle index with mid = (low + high) / 2.

Step 2: Compare middle element

It compares the middle element with the target using arr[mid] == target to check if it found the target.

Step 3: Adjust search range

If the target is greater or smaller, it moves the low or high pointer to narrow the search to one half.

Step 4: Return result

If the target is found, it returns the index; otherwise, it returns -1 after the loop ends.

Alternative Approaches

Recursive binary search

kotlin

fun binarySearchRecursive(arr: IntArray, target: Int, low: Int = 0, high: Int = arr.size - 1): Int {
    if (low > high) return -1
    val mid = (low + high) / 2
    return when {
        arr[mid] == target -> mid
        arr[mid] < target -> binarySearchRecursive(arr, target, mid + 1, high)
        else -> binarySearchRecursive(arr, target, low, mid - 1)
    }
}

fun main() {
    val arr = intArrayOf(1, 3, 5, 7, 9)
    println(binarySearchRecursive(arr, 5))
}

Uses function calls instead of a loop; easier to read but uses more stack memory.

Using Kotlin's built-in function

kotlin

fun main() {
    val arr = intArrayOf(1, 3, 5, 7, 9)
    val index = arr.binarySearch(5)
    println(index)
}

Kotlin provides a built-in <code>binarySearch</code> method that is simple and efficient.

Complexity: O(log n) time, O(1) space

Time Complexity

Binary search halves the search space each step, so it runs in logarithmic time relative to the array size.

Space Complexity

The iterative version uses constant extra space, only a few variables for pointers.

Which Approach is Fastest?

The built-in binarySearch is optimized and fastest for practical use; recursive is easier to understand but uses more memory.

Approach	Time	Space	Best For
Iterative binary search	O(log n)	O(1)	Memory efficient, fast
Recursive binary search	O(log n)	O(log n)	Clear logic, less memory efficient
Kotlin built-in binarySearch	O(log n)	O(1)	Quick and optimized for Kotlin