33. Search in Rotated Sorted Array
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7]
might become [4,5,6,7,0,1,2]
).
You are given a target value to search. If found in the array return its index, otherwise return -1
.
You may assume no duplicate exists in the array.
Your algorithm's runtime complexity must be in the order of O(log n).
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
Solution
(1) Java
class Solution {
public int search(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return -1;
}
int end = nums.length-1;
int start = 0;
while (start+1 < end) {
int mid = start + (end-start)/2;
if (nums[mid] == target) {
return mid;
}
if (nums[mid] > nums[start] && nums[mid] < nums[end]) {
if (nums[mid] > target) {
end = mid;
} else {
start = mid+1;
}
} else if (nums[mid] > nums[start]) {
if (nums[mid] > target && nums[start] <= target) {
end = mid;
} else {
start = mid+1;
}
} else {
if (nums[mid] < target && nums[end] >= target) {
start = mid+1;
} else {
end = mid;
}
}
}
if (nums[start] == target) {
return start;
} else if (nums[end] == target) {
return end;
}
return -1;
}
}
(2) Python
class Solution:
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
if not nums:
return -1
start, end = 0, len(nums)-1
while start < end:
mid = int(start + (end-start) / 2)
if nums[mid] == target:
return mid
if nums[mid] >= nums[start]:
if target >= nums[start] and target < nums[mid]:
end = mid
else:
start = mid+1
else:
if target > nums[mid] and target <= nums[end]:
start = mid+1
else:
end = mid-1
if nums[start] == target:
return start
return -1
(3) Scala