81.搜索旋转排序数组 II

搜索旋转排序数组 II

已知存在一个按非降序排列的整数数组 nums，数组中的值不必互不相同。判断给定的目标值是否存在于数组中。

解析

与第 33 题类似，但需处理重复元素导致无法判断哪半边有序的情况。

var search = function (nums, target) {
  let left = 0, right = nums.length - 1;
  while (left <= right) {
    const mid = (left + right) >> 1;
    if (nums[mid] === target) return true;
    if (nums[left] === nums[mid]) { left++; continue; }
    if (nums[left] <= nums[mid]) {
      if (target >= nums[left] && target < nums[mid]) right = mid - 1;
      else left = mid + 1;
    } else {
      if (target > nums[mid] && target <= nums[right]) left = mid + 1;
      else right = mid - 1;
    }
  }
  return false;
};