Searching algorithms

The main searching algorithm that occurs in interviews as a standalone problem or part of another problem is the Binary Search algorithm. The best case time complexity is O(1), while the average and worst case is O(log n). The worst case auxiliary space complexity of Binary Search is O(1) for the iterative implementation and O(log n) for the recursive implementation due to the call stack.

The Binary Search algorithm relies on the divide and conquer strategy. Mainly, this algorithm debuts by dividing the given array into two sub-arrays. Furthermore, it discards one of these sub-arrays and operates on the other one iteratively or recursively. In other words, at each step, this algorithm halves the search space (which is initially the whole given array).

So, these algorithms describe the steps for looking for element x in an array, a. Consider a sorted array, a, that contains 16 elements, as shown in the following image:

Figure 14.8 &...