[Searching] Binary Search — Recursion/Iteration(Full Implementation/C++)

Hello! Today, we’ll be looking at two types of searching algorithms: Linear Search(sequential search) and Interval Search.

Linear search is a searching algorithm which iterates from the start to all the way to the end one by one and check if the target exists. Hence, linear search algorithm takes O(1) time in the best case and O(n) in the worst. On the other hand, binary search, a type of interval search, targets the center element repeatedly so that for each operation, the scope of search gets halved. However, the array must be SORTED to be binary searched. Binary Search takes O(logn) time which is way more efficient than linear search. As the array size gets huge, O(logn) and O(n) are almost incomparable -> log(10000000000) ~= 33.219!!

Implementation

To implement binary search, we need to keep tracking of both the ends of array: start & end.

1. Find the mid = start + (end-start)/2
2. check if arr[mid] == target. If yes, return the index
3. check if arr[mid] > target. If yes, right = m-1. If no, left = m+1
4. repeat above steps repeatedly until start<end
5. It not found, return -1

Recursion

Iteration