问题描述

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.

在旋转数组中找目标值，注意数组中可能包含重复元素。

举个例子：

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

类似题目：

[33] Search in Rotated Sorted Array{:target=”_blank”}

解法1

Thanks [Y总]

先来看下示意图：

这道题的关键在于：将右侧与nums[0]相等的元素删除。

这样就变成了33题了。

来看下实现：

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

        int n = nums.length;
        if (n == 0) return false;

        // 1. 去除尾部的临界值
        int R = n - 1;
        while (R > 0 && nums[R] == nums[0]){
            R--;
        }

        // 2. 找到分界点
        int l = 0, r = R;
        while (l < r){
            int mid = l + r + 1>> 1;
            if (nums[mid] >= nums[0]) l = mid;
            else r = mid - 1;
        }

        // 3. 确定升序区间
        if (target >= nums[0]){
            // left
            l = 0;
        } else {
            // right
            l = r + 1;
            r = R;
        }

        // 4. 找目标值
        while (l < r){
            int mid = l + r >> 1;
            if (nums[mid] >= target) r = mid;
            else l = mid + 1;
        }

        return nums[r] == target;
    }
}

Enjoy it !