### Implementation:

1. Take an array of the sorted element in increasing order.
2. Mark the starting position of the array that is index 0 to begin and last index n to end.
3. Now find the value of mid=(begin+end)/2 and check whether array[mid]==k (number to be searched), if it is equal then return 1 i.e., found else
• if array[mid]>k then set an end to mid and repeat from step 3.
• if array[mid]<k then set begin to mid+1 and repeat from step 3.
Here to understand binary search we will be taking an Integer Array of 9 elements.
Let the element be: 1,2,3,4,5,6,7,8,9. And in this, we will be searching for k=3

The binary search uses  Pruning Strategy as we are removing half of the Array in each run.

Time Complexity
• T[n] = T[n/2] + 1
• And on solving this recurrence relation we get O(logn).
Below is the implementation of binary search in C++.

If you have some content OR material related to this OR there is an error then do share them through the comment section for which we will be thankful to you.