This problem is a nice application of binary search. The key lies in how to determine the correct half for target
. Since the array has been rotated, we now need to make some additional checks.
You may run the following code with some examples to see how it works :-)
C (0ms)
1 int search(int* nums, int numsSize, int target) { 2 int l = 0, r = numsSize - 1; 3 while (l <= r) { 4 int mid = (l & r) + ((l ^ r) >> 1); 5 if (nums[mid] == target) return mid; 6 if (nums[mid] > target) { 7 if (nums[l] <= target || nums[mid] < nums[l]) r = mid - 1; 8 else l = mid + 1; 9 } 10 else { 11 if (nums[l] > target || nums[mid] >= nums[l]) l = mid + 1; 12 else r = mid - 1; 13 } 14 } 15 return -1; 16 }
C++ (4ms)
1 class Solution { 2 public: 3 int search(vector<int>& nums, int target) { 4 int l = 0, r = nums.size() - 1; 5 while (l <= r) { 6 int mid = (l & r) + ((l ^ r) >> 1); 7 if (nums[mid] == target) return mid; 8 if (nums[mid] > target) { 9 if (nums[l] <= target || nums[mid] < nums[l]) r = mid - 1; 10 else l = mid + 1; 11 } 12 else { 13 if (nums[l] > target || nums[mid] >= nums[l]) l = mid + 1; 14 else r = mid - 1; 15 } 16 } 17 return -1; 18 } 19 };
Python (40ms)
1 class Solution: 2 # @param {integer[]} nums 3 # @param {integer} target 4 # @return {integer} 5 def search(self, nums, target): 6 l, r = 0, len(nums) - 1 7 while l <= r: 8 mid = (l & r) + ((l ^ r) >> 1) 9 if nums[mid] == target: 10 return mid 11 if nums[mid] > target: 12 if nums[l] <= target or nums[mid] < nums[l]: 13 r = mid - 1 14 else: 15 l = mid + 1 16 else: 17 if nums[l] > target or nums[mid] >= nums[l]: 18 l = mid + 1 19 else: 20 r = mid - 1 21 return -1