It is an algorithm that searches for an element in a sorted array, and it follows a Divide and Conquer algorithmic model.

Dictionary is the best example for Binary Search, since the words are in alphabetical order we don’t need to search each page by page for a word. Just, we will compare the word whether it is on front or back portion of the book, and we will keep comparing till we find the word. Similarly, binary search performs the search for an element in a sorted array.

Consider if X is an element to be searched in an array, then binary search performs the following:

- Compare X with the middle element
- If X matches with middle element, return the index of element
- Else, if X is greater than the mid-element, then X can only lie in the right half subarray after the mid-element. So, repeat for right half
- Else (X is smaller), repeat for left half

**Note:**In order to perform Binary Search, the array must be a sorted one.

### Implementation of Binary Search:

public class BinarySearch{ public static void main(String[] args){ int[] arr = new int[] {1, 2, 3, 4, 5, 6}; int X = 6; int index = binarySearch(arr, X); if(index == -1) { System.out.println("Element not found"); }else { System.out.println("Element found at index:"+index); } } private static int binarySearch(int[] arr, int X){ int low = 0; int high = arr.length - 1; while(low <= high){ int mid = (low + high)/2; if(X == arr[mid]){ // If element found, return index return mid; }else if(X > arr[mid]){ // If X is greater than Mid-element low = mid + 1; }else{ // If X is smaller than Mid-element high = mid -1; } } return -1; // If element not found, return -1 } }

In the above program, we have a sorted array of elements arr[ ] and, where X is the element to be searched. The binarySearch(int[ ], int) method initially checks X with the mid-element in the array. If X matches with mid-element, then it returns the index of mid-element and search ends. If X is greater than mid-element, then there won’t be any comparisons required to check in the first half of the array, so the search continues with the second half of the array. If X is smaller than mid-element, then there won’t be any comparisons required to check in the second half of the array, so the search continues with the first half of the array.

For each iteration, X is compared with mid-element and returning its index if matches. Else, reducing the size of array to half by eliminating elements at either left or right half of sub array and this process continues till the size of sub array to zero, nothing but no more elements to test. At the end, if X is not equal to mid-element in any of the sub array, then it returns -1 as the indication of element X is not found in the array.

Thus, the binary search algorithm can be implemented to perform the search of an element in a sorted array.

#### Time Complexity

Consider a sorted array of 1023 elements. As the binary search algorithm will eliminate half of the array for each comparison, so dividing the number of elements by 2 is equivalent to one comparison. So, 1023(2^{10} – 1) divided by 2 yields only 10 comparisons, 1,048,575(2^{20} – 1) divided by 2 yields only 20 comparisons. So, if the array contains n elements, then binary search requires log_{2} n comparisons. This results in a big O Notation of O(log n) by omitting the base.

Hence, the Time Complexity for Binary Search is **O(log n).**

Also Refer: Linear Search in Java