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: