[LeetCode每日一题]81. 搜索旋转排序数组 II

问题

已知存在一个按非降序排列的整数数组 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,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。

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

 

示例 1：

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

输出：true

示例 2：

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

输出：false

 

提示：

1 <= nums.length <= 5000

-10的四次方 <= nums[i] <= 10的四次方

题目数据保证 nums 在预先未知的某个下标上进行了旋转

-10的四次方 <= target <= 10的四次方

大水题……

思路及代码

class Solution {

public:

    bool search(vector<int>& nums, int target) {

        for (int i = 0; i < nums.size(); i++)

            if (nums[i] == target)

                return true;

        return false;

    }

};

既然题解说要用二分，那就用二分法试试看吧

这题相较于常规的二分，不同点在于它是部分非单调递减有序的（后面的有序都是指非单调递减有序），这也意味着[l, mid]和[mid,r]至少有一个区间是有序的。我们通过这个有序的区间来判断target在不在这个区间的里面（无序区间是不好判断在不在里面的），如果在，那就在有序的区间里面找（剪掉了另外一部分，这也是二分的实质——减治），不在的话，就是另外一个区间里面找（也是剪掉了一部分）

还要注意一个特殊情况，就是重复元素带来的nums[l] == nums[mid] && nums[mid] == nums[r]，这会导致无法判断区间 [l,mid] 和区间 [mid+1,r] 哪个是有序的。例如 nums=[3,1,2,3,3,3,3]，target=2，首次二分时判断区间 [0,3] 是有序的，然后确定target在不在这里面的时候就出错了。

对于这种情况，我们只能将当前二分区间的左边界加一，右边界减一，然后在新区间上继续二分查找。

class Solution {

	public:

		bool search(vector<int>& nums, int target) {

			int n = nums.size();

			int l = 0, r = n - 1, mid;

			while (l <= r) {

				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]) { //是的话，target在不在左边？

						r = mid - 1;//在左边

					} else {

						l = mid + 1;//在右边

					}

				} else { //如果左边不是单调递减有序的话，那右边一定是

					if (nums[mid] < target && target <= nums[r]) { //在不在右边？

						l = mid + 1;//在右边

					} else {

						r = mid - 1;//不在右边

					}

				}

			}

			return false;

		}

};

[LeetCode每日一题]81. 搜索旋转排序数组 II的相关教程结束。