public class Solution {
public int search(int[] nums, int target) {
int pivot = findPivot(nums);
if(pivot == 0) return binarySearch(nums, 0, nums.length  1, target);
int rightSide = binarySearch(nums, pivot, nums.length  1, target);
if(rightSide != 1) return rightSide;
int leftSide = binarySearch(nums, 0, pivot  1, target);
return leftSide;
}
private int findPivot(int[] nums) {
int left = 0;
int right = nums.length  1;
while(left < right) {
if(nums[left] < nums[right]) return left;
int mid = left + (right  left) / 2;
if(nums[left] < nums[mid]) {
left = mid + 1;
} else if(nums[left] > nums[mid] && nums[mid] < nums[right]) {
right = mid;
} else {
return right;
}
}
return left;
}
private int binarySearch(int[] nums, int start, int end, int target) {
if(start > end) return 1;
int mid = start + (end  start) / 2;
if(target == nums[mid]) return mid;
if(target < nums[mid]) return binarySearch(nums, start, mid  1, target);
return binarySearch(nums, mid + 1, end, target);
}
}
Easy to understand 1ms Java binarysearch solution


Well the findPivot function uses iterative, but its for different purpose. It's from another problem about finding the minimum element in sorted and rotated arrays (i think), so I just used that. And others are the regular binarySearch for three cases:
 the array is not rotated and element could be anywhere
 the array is rotated and the element is on the right side of the pivot
 the array is rotated and its not found on the right side, so it could be on the left.
Actually the first two cases can be merged for conciseness. And yeah you are right i should have used iterative for the "regular binary search" as well for consistency.