# 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

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.