## 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 listSorted = inputList.sorted()
println("Please, enter the number you want to find")
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) {
}
}
}
``````