https://leetcode-cn.com/problems/search-in-rotated-sorted-array/

从这题可以看出,和704题几乎是一样的,不过中间多了一些条件,看到后面你写了时间复杂度为 O(log n),一看就是二分算法,所以我们将这个数组二分,然后就可以得到哪一边是排序好的,不断区分即可得到答案,示例如下

情况 1:mid为7,左边区间是递增

[4,5,6,7,0,1,2] target = 0

此时mid为7 左边区间是递增,但是目标值不在左边 所以移动l

[4,5,6,7,0,1,2] target = 4

此时mid为7 左边区间是递增,但是目标值在左边 所以移动r

情况2:mid为0,右边区间是递增

[4,5,6,0,1,2,3] target = 2

此时mid为0 右边区间是递增,但是目标值在右边 所以移动l

[4,5,6,0,1,2,3] target = 4

此时mid为0 右边区间是递增,但是目标值不在右边 所以移动r

此时得出

function search(nums: number[], target: number): number {
  let l = 0, r = nums.length - 1;
  while (l <= r) {
    const mid = l + ((r - l) >> 1)
    //通过中点再根据l和r的坐标就可以判断出到底在递增的那一边还是递减的那一边
    const midVal = nums[mid]
    if (midVal === target) return mid
    // 这时候我们要去找递增的地方,顺便看递增的那个区间里面有没有目标值
    if (nums[l] <= midVal) {
      // 这时候左边是递增的
      if (target >= nums[l] && target <= midVal) {
        r = mid - 1
      } else {
        l = mid + 1
      }
    } else {
      // 这时候右边才是递增
      if (target <= nums[r] && target >= midVal) {
        l = mid + 1
      } else {
        r = mid - 1
      }
    }

  }
  return -1
};
Last modification:November 5th, 2021 at 11:22 pm
If you think my article is useful to you, please feel free to appreciate