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

[**33. Search in Rotated Sorted Array**](https://leetcode.com/problems/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
```

***My Solutions:***

方法1：在整个nums的范围里binary search。每一次根据反转的index在mid之前还是之后，以及target的位置，调整l和r的位置。

```java
class Solution {
    public int search(int[] nums, int target) {

    if (nums == null || nums.length == 0) return -1;
    int l = 0, r = nums.length - 1;
    while (l + 1 < r) {
        int mid = l + (r - l) / 2;
        if (nums[mid] == target) return mid;
        
        if (nums[mid] < nums[r]) { // 反转的index在mid之前,mid之后的都是递增的
            // target在mid和r之间
            if (target > nums[mid] && target <= nums[r]) l = mid;
            else r = mid;

        } else { // 反转的index在mid之后,mid之前的都是递增的
            //target在mid和l之间
            if (target >= nums[l] && target < nums[mid]) r = mid;
            else l = mid;
        }
    }
    
    if (nums[l] == target) return l;
    else if (nums[r] == target) return r;
    else return -1;
}
```

方法2：先找到转折的index，检查target在转折之前还是之后，然后在那半段里binary search。

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

    int l = 0, r = nums.length - 1;

    // 先找到转折的index
    while (l + 1 < r) {
        int mid = l + (r - l) / 2;
        if (nums[mid] > nums[r]) l = mid;
        else r = mid;
    }
    // this is the point of the largest element
    int changePoint = nums[l] > nums[r] ? l : r;

    // 找到target在转折index前还是后
    if (target >= nums[0] && target <= nums[changePoint]) {
        l = 0;
        r = changePoint;
    } else {
        l = changePoint;
        r = nums.length - 1;
    }

    // binary search
    while (l + 1 < r) {
        int mid = l + (r - l) / 2;
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) l = mid;
        else r = mid; 
    }
    if (nums[l] == target) return l;
    if (nums[r] == target) return r;
    return -1;
}
```

[**81. Search in Rotated Sorted Array II**](https://leetcode.com/problems/search-in-rotated-sorted-array-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 1:**

```
Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true
```

**Example 2:**

```
Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false
```

**Follow up:**

* This is a follow-up problem to [Search in Rotated Sorted Array](https://leetcode.com/problems/search-in-rotated-sorted-array/description/), where `nums` may contain duplicates.
* Would this affect the run-time complexity? How and why?

***My Solutions:***

和33类似，因为有duplicate number的关系，需要把duplicate的去掉。

```java
class Solution {
    public boolean search(int[] nums, int target) {
        if (nums == null || nums.length == 0) return false;
        if (nums.length == 1) return nums[0] == target;
        int l = 0, r = nums.length - 1;
        while (l + 1 < r) {
            int mid = l + (r - l ) / 2;
            if (nums[mid] == target) return true;
            // remove duplicates
            if (nums[l] == nums[mid] && nums[mid] == nums[r]) {
                l++;
                r--;
            }
            // 注意这里是连着上面的elseif，因为改变了l和r的值
            else if (nums[mid] <= nums[r]) { // 说明反转的index在mid之前，mid之后的都是递增的
                if (nums[mid] < target && target <= nums[r]) l = mid;
                else r = mid;
            } 
            else { // 说明反转的index在mid之后，mid之前的都是递增的
                if (nums[l] <= target && target < nums[mid]) r = mid;
                else l = mid;
            }
        }
        if (nums[l] == target) return true;
        if (nums[r] == target) return true;
        return false;
    }
}
```
