# 33. Search in Rotated Sorted Array

## Design

The keyword search and the time complexity needs to be in $O(logn)$ mean that the binary search approach should be applied.

### Method I

1. Find the minimum within the array nums, which is the position where rotation occurs.
2. Apply the binary search approach and mark the position where the read middle value (mid + rot) % nums.length at during each traversal. ### Method II

https://leetcode.com/problems/search-in-rotated-sorted-array/discuss/14436/Revised-Binary-Search/191339

## Implementation

### Method I

class Solution {
public int search(int[] nums, int target) {
if (nums == null || nums.length == 0) return -1;

int left = 0, right = nums.length - 1;

// Find the minimum
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[right]) { // elements to the right are always greater in a sorted array, so we narrow down the search range once this happens
left = mid + 1;
} else {
right = mid;
}
}

int rot = left;
left = 0;
right = nums.length - 1;

// Binary Search
while (left <= right) {
int mid = left + (right - left) / 2;
int realmid = (mid + rot) % nums.length;
if (nums[realmid] > target) {
right = mid - 1;
} else if (nums[realmid] < target) {
left = mid + 1;
} else {
return realmid;
}
}

return -1;
}
}

### Method II

class Solution {
public int search(int[] nums, int target) {
if (nums.length == 0 || nums == null) return -1;

int left = 0, right = nums.length - 1;

while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;

// If the array is sorted on the left part
if (nums[mid] >= nums[left]) {
// Use ">=" to make sure that the target is in the left part, then drop the right part
if (target >= nums[left] && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else { // If the array is sorted on the right part
// Use "<=" to make sure that the target is in the right part, then drop the left part
if (target <= nums[right] && target > nums[mid]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}

return -1;
}
}

## Complexity Analysis

### Method I

Time: $O(logn)$

Space: $O(1)$

### Method II

Time: $O(n)$ ($O(n/2)$)

Space: $O(1)$