Code Pumpkin

Binary Search

October 8, 2017
Posted by Pumpkin
Subscribe

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.

binary-search


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

Lets convert the above sudo code into java code.


/** 
* 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)

Binary Search vs Linear Search

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 algorithms and data structures.

That's all for this topic. If you guys have any suggestions or queries, feel free 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 🙂

Tags: , ,


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.

Total Post : 80
Subscribe
Contribute Your Articles

Interview Experiences

Related Books

Like Us On Facebook

Alexa Page Rank