2024-06-07-二分查找第二篇.md

发表于 | 分类于
搜索旋转数组中的指定值

LeetCode 33 搜索旋转排序数组

LeetCode 33 搜索旋转排序数组

这个题目从算法复杂度要求和看，可以很直观的想到二分查找，数组旋转可以关联另一个题目LeetCode 189 轮转数组。

题目34拿到的数组就是有序数组用189转完剩下的。 189也很有意思，那个数组当map用的思路，让我自己想大概得想到秃头。

这里用二分的特殊性在于：

二分要求是有序，不管是数组还是自他类型的数据，必须能明确的定义出有序，但这个数组不完全是有序的。

它由两个有序的部分组成，如果二分切开，第一次切割必然是一半有序一半无序。后面的至少也有一半是有序的，甚至切到一定程度，两边都是有序的。

所以只要在思路上偷个懒，每次都根据有序的那一边确定边界怎么收缩就可以了。

伪代码思路

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class Solution {

  public int search(int[] nums, int target) {
    int left = 0, right = nums.length - 1;

    while (left <= right) {
      int mid = left + (right - left) / 2;

      if (nums[mid] == target) {
        return mid;
      }
      if (nums[left] <= nums[mid]) {
        if (nums[left] <= target && nums[mid] > target) {
          right = mid - 1;
        } else {
          left = mid + 1;
        }
      } else {
        if (nums[mid] < target && nums[right] >= target) {
          left = mid + 1;
        } else {
          right = mid - 1;
        }
      }
    }
    return -1;
  }
}

LeetCode 81 搜索旋转排序数组 2

LeetCode 81 搜索旋转排序数组 2

这个题目是在上一道题目的基础上增加了元素可能重复。考虑影响：

1,3,3,3,3,3,3 旋转后可能是：3,3,1,3,3,3,3

第一次计算，mid=3，此时nums[left]=nums[mid]=nums[right]，在上一题目中用于判断哪一半是单调的条件不成立了。

所以针对这个情况，应该把left和right往里推进，left++;right--;

再来一个例子：

1,2,3,3,3 旋转后可能是 3,3,3,1,2

第一次计算，mid=2，此时nums[left]=nums[mid];nums[mid]!=nums[right]

在这个场景下，数组仍然能确定一侧是有序的（这里比较抽象，多举几个例子能确认，即使不是递增的，也至少是相等的）。

所以这个场景不用特殊处理。

那么针对重复元素这个关键问题的新逻辑是：

1
2
3
4
    if (nums[left] == nums[mid] && nums[mid] == nums[right]) {
      ++left;
      --right;
    }

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
  public boolean search(int[] nums, int target) {
    int n = nums.length;
    if (n == 0) {
      return false;
    }
    if (n == 1) {
      return nums[0] == target;
    }
    int left = 0, right = n - 1;
    while (left <= right) {
      int mid = (left + right) / 2;
      if (nums[mid] == target) {
        return true;
      }
      if (nums[left] == nums[mid] && nums[mid] == nums[right]) {
        ++left;
        --right;
      } else if (nums[left] <= nums[mid]) {
        if (nums[left] <= target && target < nums[mid]) {
          right = mid - 1;
        } else {
          left = mid + 1;
        }
      } else {
        if (nums[mid] < target && target <= nums[n - 1]) {
          left = mid + 1;
        } else {
          right = mid - 1;
        }
      }
    }
    return false;
  }

  
  /**
   * 手痒写的没用的解法,更可气的是这个击败了百分之百。。。。
   * <p>
   * 没办法，毕竟二分查找的变形也是O(n),崩不住
   */
  public boolean searchSLow(int[] nums, int target) {
    for (int num : nums) {
      if (num == target) {
        return true;
      }
    }
    return false;
  }
}