# Find element using binary search in sorted array

## Given an sorted array, Finding whether the element is present or not. If present, print the index of that element

### Example

input :

arr[] =  {1, 6, 7, 8, 9, 12, 14, 16, 26, 29, 36, 37, 156}

X = 6 //element to be searched

output :

element found at index 1

## Algorithm

Time Complexity: O(Logn)

Given an sorted array A with N elements, Searching for an element X with Low and High variables pointing to starting and ending of an array

1. Till Low is less than or equal to high

a. Set Mid to the Low + (High - Low)/2
b. If the element at the Mid index is equal to the searched element, return Mid
c. If the element at the Mid index is less than the searched element, than we need to search on right array, so update Low = Mid + 1
d. If the element at the Mid index is greater than the searched element, than we need to search on left array, so update High = Mid - 1

This is an iterative procedure which keeps track of the search boundaries via two variables (Low and High).

## C++ Program

``````#include <bits/stdc++.h>
using namespace std;

int Binary_search(int arr[] , int X, int low ,int high)
{

while(low <= high) // till low is less than high i.e. there is atleast one integer in the considered part of array
{

int mid = low + (high - low)/2; //compute the middle index

if(arr[mid] == X) //if equal then return
return mid;

else if ( arr[mid] < X) //if smaller then increase the lower limit
low = mid + 1;

else //if larger then decrease the upper limit
high = mid - 1;
}

return -1;
}

int main()
{
int arr[] =  { 1,6,7,8,9,12,14,16,26,29,36,37,156}; //array
int N = sizeof(arr)/sizeof(arr[0]); //size of array
int X;
cin>>X; //element to be searched
int index = Binary_search(arr,X,0,N-1); //search for the element
if(index >= 0)
cout << "Element found at index "<<index;
else