[5~6]搜索旋转排序数组

五、搜索旋转排序数组

升序排列的整数数组 nums 在某个点上进行了旋转（例如， [0,1,2,4,5,6,7] 经旋转后可能变为 [4,5,6,7,0,1,2] ）。

请你在数组中搜索 target ，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
**

输入**：nums = [4,5,6,7,0,1,2], target = 0 输出**：4

刚刚接触这道题时，并不能理解他要做什么，既然要查找目标元素在数组中的索引，直接 indexOf 不就完事了吗，有啥好设计算法的，但是注意题目中的时间复杂度 O (logn)，indexOf 时间复杂度是 O (n)，不符合题意，所以很自然的能想到二分查找算法的运用

我们随便选择一个点，将数组分为前后两部分
其中**一部分一定是有序的**!!!
知道哪里有序才能确定区间
具体步骤：
我们可以先找出 mid，然后根据 mid 来判断，mid 是在有序的部分还是无序的部分

1. 假如 mid 小于 start，则 mid 一定在右边有序部分
2. 假如 mid 大于等于 start， 则 mid 一定在左边有序部分 (注意等号的考虑)

然后我们继续判断 target 在哪一部分， 我们就可以舍弃另一部分了

var search = function (nums, target) {
  let left = 0;
  let right = nums.length - 1;
  while (left <= right) {
    const mid = left + ((right - left) >> 1);
    if (nums[mid] === target) return mid;
    // 找有序的那部分
    // [left, mid]有序
    if (nums[left] <= nums[mid]) {
      // target在左边有序的里面
      if (target >= nums[left] &&
        target < nums[mid]) right = mid - 1;
      // target不在左边有序的里面，left要收缩
      else left = mid + 1;
    }
    // [mid, right]有序
    else if (nums[mid] < nums[left]) {
      // target在右边有序里面
      if (target > nums[mid] &&
        target <= nums[right]) left = mid + 1;
      // 不在右边有序的里面
      else right = mid - 1;
    }
  }
  return -1
};

六、搜索旋转排序数组II

假设按照升序排序的数组在预先未知的某个点上进行了旋转。
例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2]

有重复元素

编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 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

/*
 * @lc app=leetcode id=33 lang=javascript
 *
 * [33] Search in Rotated Sorted Array
 */
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
const search = (nums, target) => {
  let left = 0, right = nums.length -1
  while(left<=right) {
    let mid = (left+right)>>>1
    if(nums[mid] === target) return true;
    // 存在重复数字无法判断哪边是递增的，将左端右移一位
    if(nums[left] == nums[mid]) ++ left;
    else if(nums[mid] <= nums[right]){
      // 右边递增
      if(target > nums[mid] && 
        target <= nums[right]) left = mid + 1;
      else right = mid - 1;
    } 
    else {
      // 左边递增
      if(target < nums[mid] && 
        target >= nums[left]) right = mid - 1;
      else left = mid + 1
    }
  }
  return false
};