• 困难
• 中等
• 简单

  题目描述

  假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。

编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。

来源，leetcode 每日一题 81. 搜索旋转排序数组 II

例如：

输入: nums = [2,5,6,0,0,1,2], target = 0
输出: true
输入: nums = [2,5,6,0,0,1,2], target = 3
输出: false

解题思路

1. 二分查找。
2. 条件判断
   1. 第一类： 1011110111 和 1110111101 这种。此种情况下 nums[start] == nums[mid]，分不清到底是前面有序还是后面有序，此时 start++ 即可。相当于去掉一个重复的干扰项。
   2. 第二类 2345671 这种，也就是 nums[start] < nums[mid]。此例子中就是 2 < 5；这种情况下，前半部分有序。因此如果 nums[start] <=target<nums[mid]，则在前半部分找，否则去后半部分找。
   3. 第三类: 6712345 这种，也就是 nums[start] > nums[mid]。此例子中就是 6 > 2；这种情况下，后半部分有序。因此如果 nums[mid]

      代码

      class Solution {
      public:
      bool search(vector<int>& nums, int target) {
        int begin = 0, end = nums.size() - 1;
        if (end == -1) {
            return false;
        }
        while (begin <= end) {
            int middle = (begin + end) / 2;
            if (nums[middle] == target || nums[begin] == target || nums[end] == target) {
                return true;
            } else if (middle == begin) {
                break;
            }
            if (nums[middle] == nums[begin]) {
                begin++;
                continue;
            }
            if (nums[begin] >= nums[middle]) {
                // 说明前半段是无序的
                if (nums[middle] <= target && nums[end] >= target){
                    begin = middle;
                } else {
                    end = middle;
                }
            } else if (nums[middle] >= nums[end]) {
                if (nums[begin] <= target && target <= nums[middle]) {
                    end = middle;
                } else {
                    begin = middle;
                }
            } else {
                if (nums[middle] <= target) {
                    begin = middle;
                } else {
                    end = middle;
                }
            }
        }
        return false;
      }
      };