Binary Search Algorithm in Kotlin

1. Introduction

In this tutorial, we will learn how to implement a simple Binary Search Algorithm using Kotlin programming language.

Binary Search is an efficient search algorithm that works on the principle of divide and conquer. It's used to search for an element in a sorted list. Instead of searching the list in a linear manner, binary search divides the list into halves and determines which half of the list the search key is likely to be in, reducing the number of elements to be examined by half with each step.

2. Implementation Steps

1. Initialize two pointers: low to the beginning and high to the end of the array.

2. Find the middle element of the array using (low + high) / 2.

3. If the middle element matches the key, return the middle index.

4. If the key is smaller than the middle element, set high to middle - 1 and repeat step 2.

5. If the key is larger than the middle element, set low to middle + 1 and repeat step 2.

6. If low surpasses high, the key doesn't exist in the list.

3. Implementation in Kotlin Programming

fun binarySearch(arr: List<Int>, key: Int): Int {
    var low = 0
    var high = arr.size - 1
    while (low <= high) {
        val middle = (low + high) / 2
        when {
            arr[middle] == key -> return middle
            arr[middle] < key -> low = middle + 1
            else -> high = middle - 1
        }
    }
    return -1
}
fun main() {
    val numbers = listOf(11, 22, 34, 45, 56, 78, 90)
    val key = 45
    println("List: $numbers")
    val result = binarySearch(numbers, key)
    if (result == -1) {
        println("$key is not present in the list.")
    } else {
        println("$key is present at index $result.")
    }
}

Output:

List: [11, 22, 34, 45, 56, 78, 90]
45 is present at index 3.

Explanation:

1. The Binary Search algorithm begins by examining the middle element of a sorted list.

2. If the key is equal to the middle element, the search is successful, and the position is returned.

3. If the key is smaller than the middle element, it means the desired element lies in the first half. Thus, the algorithm continues its search only in the first half.

4. Conversely, if the key is larger, the search continues only in the second half.

5. The list gets divided in half during each iteration until the key is found or until the subarray size becomes 0, indicating the key isn't present in the list.