Binary Search using recursion in C++ | CODELABS3277

Binary search is the most popular Search algorithm.It is efficient and also one of the most commonly used techniques that is used to solve problems.

If all the names in the world are written down together in order and you want to search for the position of a specific name, binary search will accomplish this in a maximum of 35 iterations. Binary search works only on a sorted set of elements. To use binary search on a collection, the collection must first be sorted.

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  Prunning 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++.

Comments