GATE 2021 CS-Set-2

In this question they given three main constraints

1. The input array is in sorted order
2. Use recursive binary search
3. Worst case number of operations

If the array is in sorted order then the worst case time complexity is O(logn)

Ex: 10, 20, 30

The binary search approach is using either recursive or iterative method is

Step-1: element = middle, the element is found and return the index.

Step-2: element > middle, search for the element in the sub-array starting from middle+1 index to n.

Step-3: element < middle, search for element in the sub-array starting from 0 index to middle -1.

Note: The worst case happens when we want to find the smallest/largest farthest node. So, it will not take more than O(logn) time.