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.
Table of Contents
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.
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.
2. Binary Search through Recursion
Now we’ll see how to achieve the same through Recursion. Below gist shows the same:
Feel free to suggest any modifications / feedback on the above implementation.