We can take advantage of the fact that the array is sorted (although rotated).

Figure out if left half is sorted
1.1. If the target is on left side, continue binary search on left half.
1.2 If not, it must of in the right half. 
Similarly figure out if right half is sorted
2.1. If the target is on right side, continue binary search on right half.
2.2 If not, it must of in the left half.public int search(int[] nums, int target) {
return search(nums, 0, nums.length1, target);
}//6,7,1,2,3,4,5
public int search (int[] nums, int first, int last, int target){
if (first > last) return 1;int mid = (first + last) / 2; if (nums[mid] == target) return mid; if (nums[first] <= nums[mid]) // Left side is sorted if (target <= nums[mid] && target >= nums[first]) // target is on left side return search (nums, first, mid  1, target); else // target is on the right side return search (nums, mid + 1, last, target); if (nums[mid] <= nums[last])// Right side is sorted if (target >= nums[mid] && target <= nums[last]) // target is right side return search (nums, mid + 1, last, target); else // target is on left side return search (nums, first, mid  1, target); return 1;
}