# 33 / 81. Search in Rotated Sorted Array I & II

Reference: Problem I & Problem II
Difficulty: Medium

My Post: Java Solution with Comments

## Problem I

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:

## Analysis

### Brute-Force

Time: $O(N)$
Space: $O(1)$

Use one binary search, but finding the pivot takes $O(N)$ time.

Time: $O(N)$
Space: $O(1)$

### Two Binary Searches

Use two binary searches. The first one is for finding the pivot.

The searching condition is nums[mid] <= nums[n - 1], which means we want to find the leftmost element that is less than the last element (the real first element).

Time: $O(\log{N})$
Space: $O(1)$

## Problem II

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]).

You are given a target value to search. If found in the array return true, otherwise return false.

Example:

The original solution is not applicable when finding the pivot.

Example:

• [1, 3, <1>, 1, 1]
• [1, 1, 1, 3, <1>, 1, 1, 1, 1]

The index of the pivot will be $0$, which is not correct.

The solution is to do the processing as follows:

Note:

• nums could be empty (length == 0) but not null.

Time: $O(\log{N})$

• $O(N)$ in the worst case (pre-processing).

Space: $O(1)$

Do it in one loop:

I don’t like this version. Not clear.

Comment
Junhao Wang
a software engineering cat