81.搜索旋转排序数组II

链接：81.搜索旋转排序数组II
难度：Medium
标签：数组、二分查找
简介：给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。

题解 1 - typescript

• 编辑时间：2021-07-23
• 执行用时：80ms
• 内存消耗：39.4MB
• 编程语言：typescript
• 解法介绍：二分查找。

function search(nums: number[], target: number): boolean {
  let l = 0;
  let r = nums.length - 1;
  if (nums[l] === target || nums[r] === target) return true;
  while (l < r) {
    while (l < r && nums[l] !== target && nums[l] === nums[r]) {
      l++;
      r--;
    }
    if (nums[l] === target || nums[r] === target) return true;
    const mid = (r + l) >> 1;
    const midNum = nums[mid];
    if (midNum === target) return true;
    if (midNum <= nums[r]) {
      if (midNum <= target && target <= nums[r]) l = mid + 1;
      else r = mid - 1;
    } else {
      if (nums[l] <= target && target <= midNum) r = mid - 1;
      else l = mid + 1;
    }
  }
  return false;
}

题解 2 - typescript

• 编辑时间：2021-04-07
• 执行用时：84ms
• 内存消耗：39.8MB
• 编程语言：typescript
• 解法介绍：先获取偏移值再进行二分查找。

function search(nums: number[], target: number): boolean {
  const len = nums.length;
  let k = 1;
  for (; k < len; k++) if (nums[k - 1] > nums[k]) break;
  const find = (start: number, end: number): boolean => {
    if (start > end) return false;
    const mid = ~~((start + end) / 2);
    const num = nums[(mid + k) % len];
    if (num > target) return find(start, mid - 1);
    else if (num < target) return find(mid + 1, end);
    else return true;
  };
  return find(0, len - 1);
}