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

发表于 | 分类于
二分基础+简单题

基础说明

二分查找（binary search）适用于在已经排序的数组中或者其他有严格顺序关系的数据结构中查找某个特定的元素，核心的方法是每次将查找范围缩减一半。

思路说明：

  • 初始化边界：初始左边界left=0，右边界right=arr.length-1
  • 中间位置始终是：mid = left+(left+right)/2
  • 比较中间值：
    • 如果arr[mid]==target,查找结束，返回
    • 如果arr[mid]<=target,边界往右推left=mid+1,继续比较
    • 如果arr[mid]>=target,边界往左推right=mid-1,继续比较
  • 重复比较的动作直至找到目标值或者left>right

时间复杂度：O(log n) 空间复杂度：O(1)

LeetCode 704 二分查找

LeetCode 704 二分查找

题目就叫二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {

  public int search(int[] nums, int target) {
    int ans = -1;
    int left = 0, right = nums.length - 1, mid;
    while (left <= right) {
      mid = left + ((right - left) >> 1);
      if (nums[mid] == target) {
        return mid;
      } else if (target < nums[mid]) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    }
    return ans;
  }
}

LeetCode 35 搜索插入位置

LeetCode 35 搜索插入位置

二分查找的小变种，需要在标准解法里面注意一下target是小于所有制还是大于所有值，所以要么默认最大，每次变小，要么就默认最小，每次变大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {

  public int searchInsert(int[] nums, int target) {
    int ans = nums.length;
    int left = 0, right = nums.length - 1, mid;
    while (left <= right) {
      mid = left + ((right - left) >> 1);
      if (target <= nums[mid]) {
        ans = mid;
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    }
    return ans;
  }

}

LeetCode 278 第一个错误版本

LeetCode 278 第一个错误版本

这个题目算是二分的一个变种，把数组变成了数字，返回第一个错误的版本而不是下标，其他的没有差别。

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
51
52
53
54
55
public class Solution {

  public int firstBadVersion(int n) {
    int left = 1, right = n, mid;
    while (left <= right) {
      mid = left + ((right - left) >> 1);
      if (!isBadVersion(mid)) {
        left = mid + 1;
      } else {
        if (mid == 1 || !isBadVersion(mid - 1)) {
          return mid;
        } else {

          right = mid - 1;
        }
      }
    }
    return left;
  }


  /**
   * 按照二分的标准思路来的，但是这样子调用isBadVersion()太多，可以优化一下
   */
  public int firstBadVersionBase(int n) {
    int left = 1, right = n, ans = n, mid;
    while (left <= right) {
      mid = left + ((right - left) >> 1);
      if ((isBadVersion(mid) && !isBadVersion(mid - 1) || isBadVersion(mid - 1))) {
        ans = mid;
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    }
    return ans;
  }

  /**
   * 朴素解法，但肯定是不过的
   *
   */
  public int firstBadVersionSlow(int n) {
    if (n == 1) {
      return n;
    }
    while (n > 0) {
      if (!isBadVersion(n)) {
        break;
      }
      n--;
    }
    return n + 1;
  }
}