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.

Thank You for Reading