Binary Search in Kotlin | Data Structures

Binary Search is a search algorithm that finds the specified index of a value within a sorted array only. In effect it is trying to find the meaning of a word in a dictionary or description of an item in an encyclopedia.

How does it work?

You have a sorted array consisting of X elements, and you input the value to be found in it. The algorithm compares your input value with the key value of the array's middle element. So here we have 3 scenarios

If input key value matches the key value of the middle element, and it's index is returned.

If input key value is lesser than the key value of middle element, do a search on the sub array to the left of the middle element.

Similarly if the input key value is greater than key value of middle element, do a search on the sub array to the right of the middle element.

There are two ways in which this can be implemented

Recursive :

A more straightforward implementation of binary search, here it determines a mid point between the highest and lowest indices in the array.

Here basing on whether the key value is higher or lower than key value of mid point, it does a recursive search on the subset of the array, till the values are matched.

Iterative :

Implements the same logic, but instead of invoking the same method, here we have an infinite loop, which keeps executing as long as the upper indice is greater than or equal to the lower indices.

If the key value of mid point is less than input key value, you increase the min index to search upper sub array, else if lower, you decrease the max index to search lower sub array.


class BinarySearch {
    fun doBinarySearch () {
        println("Please, enter some integer numbers using space bar")
        val inputList = readLine()!!.split(' ').map(String::toInt)
        val listSorted = inputList.sorted()
        println("Please, enter the number you want to find")
        val item = readLine()!!.toInt()
        var low = 0
        var high = listSorted.size - 1
        var stepCount = 0
        var isItemFound = false
        while (low <= high) {
            val mid = (low + high) / 2
            val guess = listSorted[mid]
            stepCount++
            when {
                guess == item -> {
                    println("Your number $item was found in $stepCount steps")
                    isItemFound = true
                }
                guess > item -> high = mid -1
                else -> low = mid + 1
            }
            if (isItemFound) break //"break" is not allowed in "when" statement
        }
        if (!isItemFound) {
            println("Your number wasn't found")
        }
    }
}			

aaaaaaaaaaaaa
Comment / Suggestion Section
Point our Mistakes and Post Your Suggestions

Recent Addition

new tutorial Selenium Online Training : Our next online training course for Selenium with Java starts from 17th December 2018.

You can attend first 3 classes for free, the total course fee is INR 10,000

The course time would be 8.00 PM(IST) for the first three classes

If you are interested to learn, then you can join the course by sending email to chercher.tech@gmail.com

or Register below


 
Join My Facebook Group
Join Group