Binary Search
There are many ways to search for the element from the given sorted array of n elements. Linear search, binary search, Fibonacci Search are few of them. In this article, we will see the binary search in detail. Binary search enables searching of the element in O(log n) time complexity.
Binary Search (definition)
Search a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half.
Below is an animated representation of the same.
Algorithm
Sudo code for binary search can be written as below using recursion:
function binarySearch(a, value, left, right)
if right < left
return not found
mid := floor((right-left)/2)+left
if a[mid] = value
return mid
if value < a[mid]
return binarySearch(a, value, left, mid-1)
else
return binarySearch(a, value, mid+1, right)
Java Program Implemention
/**
* internal method which implement recursive binary search algorithm
*
* @param array
* @param start
* @param end
* @param target
* @return index of target element or -1 if not found
*/
private static int binarySearch(int[] array, int start, int end, int target) {
int middle = (start + end) / 2;
if (end < start) {
return -1;
}
if (target == array[middle]) {
return middle;
} else if (target < array[middle]) {
return binarySearch(array, start, middle - 1, target);
} else {
return binarySearch(array, middle + 1, end, target);
}
}
}Here we have implemented binary search using recursion call of the function. There is one more way of implementing binary search which is as using a loop. Try to implement the same yourself and if you need any help with that you can always comment on the article, we will be happy to help you out get it solved.
Binary Search vs Sequential (Linear) Search
1) Time Complexity of Binary Search algorithm is O(logn), whereas time complexity of Sequential Search is O(n)
2) Binary Search can only be applied to Sorted List, whereas Sequential search can also be applied to unsorted list and provide same time complexity i.e. O(n)
These algorithms are for searching elements in array or linear list, however we have also written articles on various Graph Search algorithms like Breadth First Search and Depth First Search. You can also go through our other articles on different
That's all for this topic. If you guys have any suggestions or queries, feel free to drop a comment. We would be happy to add that in our post. You can also contribute your articles by creating contributor account here.
Happy Learning 🙂
If you like the content on CodePumpkin and if you wish to do something for the community and the planet Earth, you can donate to our campaign for planting more trees at CodePumpkin Cauvery Calling Campaign.
We may not get time to plant a tree, but we can definitely donate ₹42 per Tree.
About the Author
Tags: Algorithms, Binary Search, Searching Algorithms
Comments and Queries
If you want someone to read your code, please put the code inside <pre><code> and </code></pre> tags. For example:<pre><code class="java"> String foo = "bar"; </code></pre>For more information on supported HTML tags in disqus comment, click here.
