class Solution {
public:
int search(int A[], int n, int target) {
int lo=0,hi=n1;
// find the index of the smallest value using binary search.
// Loop will terminate since mid < hi, and lo or hi will shrink by at least 1.
// Proof by contradiction that mid < hi: if mid==hi, then lo==hi and loop would have been terminated.
while(lo<hi){
int mid=(lo+hi)/2;
if(A[mid]>A[hi]) lo=mid+1;
else hi=mid;
}
// lo==hi is the index of the smallest value and also the number of places rotated.
int rot=lo;
lo=0;hi=n1;
// The usual binary search and accounting for rotation.
while(lo<=hi){
int mid=(lo+hi)/2;
int realmid=(mid+rot)%n;
if(A[realmid]==target)return realmid;
if(A[realmid]<target)lo=mid+1;
else hi=mid1;
}
return 1;
}
};
Concise O(log N) Binary search solution


Well done! Based on your approach, I have beaten 100% of java submission. Here's my java code:
public int search(int[] nums, int target) { int minIdx = findMinIdx(nums); if (target == nums[minIdx]) return minIdx; int m = nums.length; int start = (target <= nums[m  1]) ? minIdx : 0; int end = (target > nums[m  1]) ? minIdx : m  1; while (start <= end) { int mid = start + (end  start) / 2; if (nums[mid] == target) return mid; else if (target > nums[mid]) start = mid + 1; else end = mid  1; } return 1; } public int findMinIdx(int[] nums) { int start = 0, end = nums.length  1; while (start < end) { int mid = start + (end  start) / 2; if (nums[mid] > nums[end]) start = mid + 1; else end = mid; } return start; }

I think the second while loop can be optimised. Given that you have already known the left hand sub array and the right hand sub array, so we don't have to set low = 0 and high = n  1, we can set the arrange more precisely to [0  smallest_index] or [smallest_index, high](whether in left hand or in right hand or not exists ). Am I right?

This code is much more readble:
public class Solution { public int search(int[] nums, int target) { int start = 0, end = nums.length  1; while (start < end) { int mid = (start + end) / 2; if (nums[mid] > nums[end]) { // eg. 3,4,5,6,1,2 if (target > nums[mid]  target <= nums[end]) { start = mid + 1; } else { end = mid; } } else { // eg. 5,6,1,2,3,4 if (target > nums[mid] && target <= nums[end]) { start = mid + 1; } else { end = mid; } } } if (start == end && target != nums[start]) return 1; return start; } }

Is the performance of this double binary search algo is better than the single binary search algo in the link below? Why?
https://leetcode.com/discuss/41134/javaacsolutionusingoncebinarysearch

Is the performance of this double binary search algo is better than the single binary search algo in the link below? Why?
https://leetcode.com/discuss/41134/javaacsolutionusingoncebinarysearch