Monday, May 27, 2024
HomeAlgorithmsBinary Search using Kotlin - Searching Algorithms #1

Binary Search using Kotlin – Searching Algorithms #1

-

In this article, let us discuss one more Algorithm – Binary Search which is the most frequently asked Algorithms during Interviews. Let us discuss about it in brief and how to implement its algorithm using Kotlin Programming Language.

According to Wikipedia, A Binary Search is a search algorithm that finds the position of a target value within a sorted array. The algorithm compares the target element with the middle element of the array. If the target element is greater than middle element, the algorithm will be reapplied to the right of the array. If the target element is less than middle element, then the algorithm is again applied to the left of the array. Note that this algorithm is to be applied only on the sorted array.

Related Links

[adinserter block=”3″]

Advantages

Binary Search is significantly faster than that of Linear search. While Linear search takes O(n) time to search for an element in worst case, Binary search only takes O(log n) to search an element. For example, if there are more elements, it will significantly reduces the amount of time taken to find the element from the sorted array.

Algorithm

We will discuss here, the two ways of achieving Binary Search Implementation –

1. Binary Search through Iteration

Below gist shows us how to achieve the Algorithm through iteration. Here our goal is simple: Firstly to read the array and the element to be searched from the user input and print the position of element in the array. Here is the iterative implementation of the same. Code is commented wherever I find it necessary. Feel free to modify in gist / comment if anything more required.


package main.algorithms.searching
fun main(args: Array<String>) {
val input = readLine()!!.trim().split(" ").map { it -> it.toInt() }.toIntArray() // to read an array (from user input)
val eleToSearch = readLine()!!.trim().toInt() // to read the element to be searched (from user input)
val pos = binarySearchIterative(input, eleToSearch)
if(pos >= 0 ) {
println(pos) // to print position at last
} else {
println("Position not found")
}
}
fun binarySearchIterative(input: IntArray, eleToSearch: Int) : Int{
var low = 0
var high = input.size-1
var mid:Int
while(low <= high) {
mid = low + ((high – low) / 2)
when {
eleToSearch >input[mid] -> low = mid+1 // element is greater than middle element of array, so it will be in right half of array
eleToSearch == input[mid] -> return mid // found the element
eleToSearch < input[mid] -> high = mid-1 //element is less than middle element of array, so it will be in left half of the array.
}
}
return -1
}

view raw

BinarySearch.kt

hosted with ❤ by GitHub

[adinserter block=”3″]
2. Binary Search through Recursion

Now we’ll see how to achieve the same through Recursion. Below gist shows the same:


package main.algorithms.searching
fun main(args: Array<String>) {
val input = readLine()!!.trim().split(" ").map { it -> it.toInt() }.toIntArray() // to read an array (from user input)
val eleToSearch = readLine()!!.trim().toInt() // to read the element to be searched (from user input)
val pos = binarySearchRecursive(input, eleToSearch, 0, input.size -1)
if(pos >= 0 ) {
println(pos) // to print position at last
} else {
println("Position not found")
}
}
fun binarySearchRecursive(input: IntArray, eleToSearch: Int, low:Int, high:Int): Int {
while(low <=high) {
val mid = (low + high) /2
when {
eleToSearch > input[mid] -> return binarySearchRecursive(input, eleToSearch, mid+1, high) // element is greater than middle element of array, so it will be in right half. Recursion will call the right half again
eleToSearch < input[mid] -> return binarySearchRecursive(input, eleToSearch, low, mid-1) //element is less than middle element of array, so it will be in left half of the array. Recursion will call the left half again.
eleToSearch == input[mid] -> return mid // element found.
}
}
return -1
}

Feel free to suggest any modifications / feedback on the above implementation.

 

LEAVE A REPLY

Please enter your comment!
Please enter your name here

This site uses Akismet to reduce spam. Learn how your comment data is processed.

LATEST POSTS

3 Sum | Leetcode #15 | 100 Days of Code Day 10

Today we are going to solve 3 Sum - our first Medium Level Array problem from Coderefer DSA Sheet. If you are new to this...

Best Time to Buy and Sell Stock – Day 7 | 100 Days of Code

Welcome to Day 7 of 100 Days of Code where today we solve yet another most frequently asked easy array problem called - Best Time...

Contains Duplicate – Day 8 | 100 Days of Code

Welcome to Day 8 of 100 Days of Code and today we are going to solve yet another easy-level problem - Contains Duplicate as part...

Two Sum – Day 6 | 100 Days of Code

Welcome to Day 6 of 100 Days of Code where we solve the most frequently asked Easy level Array problem - Two Sum. Let us...

Follow us

1,358FansLike
10FollowersFollow
398SubscribersSubscribe

Most Popular