Search in Rotated Sorted Array
class Solution {
public int search(int[] nums, int target) {
if(nums.length == 0) return -1;
int l = 0;
int r = nums.length - 1;
while((l+1) < r){
int mid = (l+ r) / 2;
if(nums[mid] > nums[l]) {
if(nums[mid] > target && nums[l] <= target){
r = mid;
} else {
l = mid;
}
} else {
if(nums[mid] < target && nums[r] >= target){
l = mid;
} else {
r = mid;
}
}
}
if(nums[l] == target) return l;
if(nums[r] == target) return r;
return -1;
}
}class Solution:
# @param {integer[]} nums
# @param {integer} target
# @return {integer}
def search(self, nums, target):
if not nums:
return -1
return self.binarySearch(nums, target, 0, len(nums)-1)
def binarySearch(self, nums, target, start, end):
if end < start:
return -1
mid = (start+end)/2
if nums[mid] == target:
return mid
if nums[start] <= target < nums[mid]: # left side is sorted and has target
return self.binarySearch(nums, target, start, mid-1)
elif nums[mid] < target <= nums[end]: # right side is sorted and has target
return self.binarySearch(nums, target, mid+1, end)
elif nums[mid] > nums[end]: # right side is pivoted
return self.binarySearch(nums, target, mid+1, end)
else: # left side is pivoted
return self.binarySearch(nums, target, start, mid-1)
最后更新于
这有帮助吗？