## 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 cout<<"Element not found in the array"; return 0; }