Shifted Binary Search Problem
--
The problem asks you to find a number from a sorted array but all the numbers has been shifted by some amount either left or right.For Example:{9, 19, 21, 2, 8} the array is sorted from index 0 to 2 and then we have the value 2 which is less than 21 and then again from index 3 to 4 the array is sorted again. Notice that for the array to be sorted, all the values from index 0 to 2 are supposed to come after the value 8 which is at index 4. So, the problem give you this kind of shifted array and asks you to find a given value from this array. You can find this problem in leetcode. Before you see the solution try it by yourself.
Solution Approach
As the name of the post suggests, we will try to use binary search to solve this problem. In binary search we initialize a right and left pointer, using those two we calculate a middle pointer that point to the middle of the array and compare its value to our searched value and depending on weather the value is smaller or greater than the searched value, we explore half of the array and eliminate the other half. So, for this problem if our searched value is 2 and given array is: {9,19,21,2,8}
If we declare our left and right pointer we get:
If we use basic binary search, we will eliminate the right half of the array as the value which is pointed by the middle pointer is greater than our target value. But for this array if we eliminate right half we are eliminating our target value. So, we can not use normal binary search here.
We will still use binary search but change it a little bit. So, instead of comparing target value to the middle element, we will compare value of left pointer with the middle element and if it is less than of equal to the middle element, we’ll check if the searched value(2) is smaller than 21 and greater than or equal to 9 then we can eliminate the right half and explore the right side like we used to do in binary search. Otherwise, we’ll eliminate the left half and explore right half.
But if our array was: {9, 22, 1, 2,8}ans searched element was 22, then we would compare middle and left pointer ans see that 9 is not smaller than 1. So, we have to compare middle and right pointer and 8 is greater than 1 but, 22 is not in between these two values. That means we can not eliminate the left half because 22 is in the left half so, we will update the right pointer.
Code Implementation:
As this code is a variation of binary search, it has same complexity as binary search.
Time Complexity: O(log n)
Space Complexity: O(1)
