# Binary Search

October 8, 2017
Posted by Pumpkin

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

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

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>
```