Shifted Binary Search

• Time : O(logn)
• Space : O(1)

#include <vector>
using namespace std;

int shiftedBinarySearch(vector<int> array, int target) {
  int n = array.size(), l = 0, r = n - 1;
	while(l < r) {
		int m = (l + r) / 2;
		if(array[m] > array[r]) l = m + 1;
		else r = m;
	}
	
	int small = r;
	l = 0, r = n - 1;
	
	while(l <= r) {
		int m = (l + r) / 2;
		int mid = (m + small) % n;
		if(array[mid] == target) return mid;
		
		if(array[mid] > target) r = m - 1;
		else l = m + 1;
	}
  return -1;
}