# Binary search

Binary Search is a searching algorithm for searching an element in a sorted list or array. it is more efficient than linear search as its complexity is ÎŸ(log n). This search algorithm works on the principle of divide and conquer.

Algorithm: half of elements are ignored after each comparision

let X be the element to be searched

- Compare X with the middle element of the array.
- If X is same as middle element return the mid index.
- Else If X is greater than the mid element, then X will lie in right half of mid element. So we now search X in only the right half and left half is ignored
- Else if X is smaller, search for X in the left half ignore the right half.

Middle element can be found by using any of the two formulas:

1) mid= (low+ high) /2

Or

2) mid=low+(high-low) /2

**how binary search works?**

it is mandatory for the target array to be sorted,we need to search the location of value 23 using binary search.

First, we shall determine mid of the array by using this formula :

`mid = low + (high - low) / 2`

Here it is, 0 + (9 - 0 ) / 2 = 4 (integer value of 4.5). So, 4 is the mid of the array.

now we should compare the mid with the element to be searched as 16<23 we should search in the right half now and ignore the left half

again when we calculate the mid using above formula we get mid as 7 , as the element to be searched is smaller than the mid ,56>23 so we now search in the left half of the mid.

now left is 5 + (6- 5 ) / 2 = 5(integer value of 5.5) so mid is 5, now the element to be searched is equal to mid so return mid

the element to be searched is in 5th index

Iterative Function:

n is the no. of elements in array

and is element to be searched

int binarySearch(int arr[],int n,int x) { int l=0; int r=n-1; while (l <= r) { int m = l + (r - l) / 2; // Check if x is present at mid if (arr[m] == x) return m; // If x greater, ignore left half if (arr[m] < x) l = m + 1; // If x is smaller, ignore right half else r = m - 1; } // if we reach here, then element was // not present return -1; }

Recursive Function:

**int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l) {
int mid = l + (r - l) / 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, l, mid - 1, x);
// Else the element can only be present
// in right subarray
return binarySearch(arr, mid + 1, r, x);
}
// We reach here when element is not
// present in array
return -1;
}
int main()
{
int n; cin>>n;
int x; cin>>x;
int arr[n];
for(int i=0;i<n;i++)
cin>>arr[i];
cout<<binarySearch(a,0,n-1,x);
}**

Time Complexity: O(Log N)