Search in Rotated Sorted Array
Problem: Search in Rotated Sorted Array
Actually there's only four situations. Since the array is rotated, two parts aside middle should be like one sorted and another rotated. This makes two situations, while the target is either left or right, which makes another independent 2 situations. 2 times 2 makes 4 situations. Here's a solution hold tight to that.
However, my solution is kind of silly. Once we find the answer is in rotated part, I reduced the boundary to achieve the sorted part in the rotated part.
Code in Python:
class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
if not nums: return -1
if len(nums) == 1: return 0 if nums[0] == target else -1
i, j = 0, len(nums)-1
while i < j:
mid = (i + j) / 2
if (i == mid or j == mid) and target not in nums[i:j+1]: return -1
if nums[mid] == target: return mid
if nums[i] == target: return i
if nums[j] == target: return j
elif nums[i] < nums[j]:
if target < nums[mid]: j = mid
elif target > nums[mid]: i = mid
else:
if target < nums[mid]: i += 1
else: j -= 1
return -1
Code in Java:
public class Solution {
public int search(int[] nums, int target) {
if (nums.length == 0) return -1;
if (nums.length == 1 && nums[0] == target) return 0;
if (nums.length == 1) return -1;
int i = 0, j = nums.length-1;
while (i < j) {
int m = (i+j+1)/2;
if (nums[m] == target) return m;
if (nums[i] == target) return i;
if (nums[j] == target) return j;
if (target < nums[j] && nums[m] > nums[j]) i = m+1;
else if (nums[m] > target) j = m-1;
else if (target > nums[i] && nums[m] < nums[i]) j = m-1;
else i = m+1;
}
return -1;
}
}