# How to apply Binary Search on an Array

The prerequisite for binary search is that the array should be sorted. Firstly we compare the item to be searched with the middle element of the array. If the item is found there, our search finishes successfully otherwise the array is divided into two halves, first half contains all element to the left of the middle element and other one contains of all the elements to the right side of the middle element.

**Idea Behind the Binary Search**

Since the array is sorted all the elements in the left half is less than the middle element and all the elements in the second half is larger than the middle element. If the item is to be searched is less than the middle element, it is searched in the left half otherwise, it is searched in the right half of the array.

Now search proceeds in the smaller portion of the array. If the item is same as the middle element, search finishes otherwise again the sub array is divided into two halves and the search is performed in one of these halves. This process of comparing the item with the middle element and dividing the array will continue till we find the required item or get a portion which does not have any element. From the above description it is natural client for recursive implementation.

Let us understand binary search with some example. Let us take a sorted array of \(20\) elements and suppose we search for element \(41\). In each step we divided the array into two halves. If the array length is even we have two middle element, we will take first element as middle element. The total search space in each step is shown in blue color, middle element is shown in yellow color and when the search success the target element shown in green color.

Let us search for element \(62\).

**Recursive Implementation of Binary Search**

Suppose we want to search for an element **x** in an array. Then

- Compare
**x**with the middle element. - If
**x**matches with middle element, we return the**mid index**. - Else If
**x**is greater than the mid element, then**x**can only lie in right half sub array after the mid element. So we recur for**right half**. - Else (
**x**is smaller) recur for the left half.

#include<stdio.h> // A recursive binary search function. It returns location of x in // given array arr[left...right] is present, otherwise -1 int binarySearch(int arr[], int left, int right, int x) { if (right >= left) { int mid = left + (right - left)/2; // If the element is present at the middle itself if (arr[mid] == x) return mid; // If element is smaller than mid, then it can only be present // in left subarray if (arr[mid] > x) return binarySearch(arr, left, mid-1, x); // Else the element can only be present in right subarray return binarySearch(arr, mid+1, right, x); } // We reach here when element is not present in array return -1; } int main(void) { int arr[] = {2, 3, 4, 10, 40}; int n = sizeof(arr)/ sizeof(arr[0]); int x = 10; int result = binarySearch(arr, 0, n-1, x); (result == -1)? printf("Element is not present in array") : printf("Element is present at index %d", result); return 0; }

**Iterative Implementation of Binary Search**

#include<stdio.h> // A iterative binary search function. It returns location of x in // given array arr[left...right] if present, otherwise -1 int binarySearch(int arr[], int left, int right, int x) { while (left <= right) { int mid = left + (right - left)/2; // Check if x is present at mid if (arr[mid] == x) return mid; // If x greater, ignore left half if (arr[mid] < x) left = mid + 1; // If x is smaller, ignore right half else right = mid - 1; } // if we reach here, then element was not present return -1; } int main(void) { int arr[] = {2, 3, 4, 10, 40}; int n = sizeof(arr)/ sizeof(arr[0]); int x = 10; int result = binarySearch(arr, 0, n-1, x); (result == -1)? printf("Element is not present in array") : printf("Element is present at index %d", result); return 0; }

**Time Complexity of Binary Search**

Since in each step of binary search we reduce the search space by one half and we need only one comparison to do this reduction( comparing to the middle element) The recurrence relation of binary search is given by

$$\bbox[pink,5px]{T(n) = T(\frac{n}{2}) + 1}$$

Solving this by Master theorem, we get

$$\bbox[pink,5px]{T(n) = \mathcal O(\log n)} $$

It is clear from the above expression that binary search is more efficient than the linear search. For an array of about \(1000000\) elements maximum number of comparison required in binary search to find any element would be only \(20\), whereas in linear search it takes \(1000000\) comparison.

This article is contributed by Ram Kripal. If you like eLgo Academy and would like to contribute, you can mail your article to admin@elgoacademy.org. See your article appearing on the eLgo Academy page and help other Geeks. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.