#yyds干货盘点# LeetCode面试题：搜索旋转排序数组 II

1.简述：

已知有一个按非降序排列的整数组 nums ，数组中的值不必相互不同。

在传递给函数之前，nums 在预先未知的下标中 k（0 <= k < nums.length）上进行了 旋转 ，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0，1，2，4，4，4，5，6，7] 在下标 5 旋转后可能会变成 [4，5，6，6，7，0，1，2，4] 。

给你 旋转后 的数组 nums 和一个整数 target ，请编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 这个目标值存在于中间 target ，则返回 true ，否则返回 false 。

您必须尽可能减少整个操作步骤。

示例1：

输入：nums = [2，5，6，0，1，2]， target = 0

输出：true

示例2：

输入：nums = [2，5，6，0，1，2]， target = 3

输出：false

2.实现代码：

class Solution {    public boolean search(int[] nums, int target) {        int n = nums.length;        if (n == 0) {            return false;        }        if (n == 1) {            return nums[0] == target;        }        int l = 0, r = n - 1;        while (l <= r) {            int mid = (l + r) / 2;            if (nums[mid] == target) {                return true;            }            if (nums[l] == nums[mid] && nums[mid] == nums[r]) {                ++l;                --r;            } else if (nums[l] <= nums[mid]) {                if (nums[l] <= target && target < nums[mid]) {                    r = mid - 1;                } else {                    l = mid + 1;                }            } else {                if (nums[mid] < target && target <= nums[n - 1]) {                    l = mid + 1;                } else {                    r = mid - 1;                }            }        }        return false;    }}