Modified Binary Search

Question 1

Order-agnostic Binary Search

Problem Statement
Given a sorted array of numbers, find if a given number ‘key’ is present in the array. Though we know that the array is sorted, we don’t know if it’s sorted in ascending or descending order. You should assume that the array can have duplicates.
Write a function to return the index of the ‘key’ if it is present in the array, otherwise return -1.

TC – O(logN)
SC – O(1)

Answer 1

Pseudo code:
1. Point start to the first index and end is pointing to the last index of the input array.
2. Find middle
Middle = start + (end-start)/2;
3. Next, we will see if the ‘key’ is equal to the number at index middle. If it is equal we return middle as the required index.
4. If ‘key’ is not equal to number at index middle, we have to check two things:
4.1. If key < arr[middle], then we can conclude that the key will be smaller than all the numbers after index middle as the array is sorted in the ascending order. Hence, we can reduce our search to end = mid - 1.
4.2. If key > arr[middle], then we can conclude that the key will be greater than all numbers before index middle as the array is sorted in the ascending order. Hence, we can reduce our search to start = mid + 1.
5. We will repeat steps 2-4 with new ranges of start to end. If at any time start becomes

Takeaway: If array is sorted in descending order then 4.1 & 4.2 logic will be opposite.