# Binary Search Algorithm with C++ Code | Data Structures & Algorithms

Binary search algorithm falls under the category of interval search algorithms. This algorithm is much more efficient compared to linear search algorithm. Binary search only works on sorted data structures. This algorithm repeatedly target the center of the sorted data structure & divide the search space into half till the match is found.
The time complexity of binary search algorithm is O(Log n).

##### Working –

1. Search the sorted array by repeatedly dividing the search interval in half
2. Begin with an interval covering the whole array.
3. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half.
4. Otherwise narrow it to the upper half.
5. Repeatedly check until the value is found or the interval is empty.

##### Algorithm to perform Binary Search –
1. Take input array, left, right & x
2. START LOOP – while(left greater than or equal to right)
• mid = left + (right-left)/2
• if(arr[mid]==x) then
• return m
• else if(arr[mid] less than x) then
• left = m + 1
• else
• right= mid – 1
3. END LOOP
4. return -1