JavaDriver
YoungAnn
2022-10-11
目录

二分查找

# 二分查找

int binarySearch(int[] nums, int target) {
    int left = 0; 
    int right = nums.length - 1; // 注意

    while(left <= right) {
        int mid = left + (right - left) / 2;
        if(nums[mid] == target)
            return mid; 
        else if (nums[mid] < target)
            left = mid + 1; // 注意
        else if (nums[mid] > target)
            right = mid - 1; // 注意
    }
    return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

1、为什么 while 循环的条件中是 <=，而不是 <？

答：因为初始化 right 的赋值是 nums.length - 1，即最后一个元素的索引，而不是 nums.length。

2、为什么 left = mid + 1，right = mid - 1？我看有的代码是 right = mid 或者 left = mid，没有这些加加减减，到底怎么回事，怎么判断？

答：这也是二分查找的一个难点，不过只要你能理解前面的内容，就能够很容易判断。

刚才明确了「搜索区间」这个概念，而且本算法的搜索区间是两端都闭的，即 [left, right]。那么当我们发现索引 mid 不是要找的 target 时，下一步应该去搜索哪里呢？

# 寻找左侧边界的二分搜索

public static int getLeftNums(int[] nums,int target) {
  int left = 0;
  int right = nums.length;
  while (left < right) {
    int mid = left + (right - left) / 2;
    if (nums[mid] == target) {
      right = mid;
    } else if (nums[mid] > target) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
  return left;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

1、为什么 while 中是 < 而不是 <=?

答：用相同的方法分析，因为 right = nums.length 而不是 nums.length - 1。因此每次循环的「搜索区间」是 [left, right) 左闭右开。

while(left < right) 终止的条件是 left == right，此时搜索区间 [left, left) 为空，所以可以正确终止。

为什么 left = mid + 1，right = mid ？和之前的算法不一样？

答：这个很好解释，因为我们的「搜索区间」是 [left, right) 左闭右开，所以当 nums[mid] 被检测之后，下一步的搜索区间应该去掉 mid 分割成两个区间，即 [left, mid) 或 [mid + 1, right)。

4、为什么该算法能够搜索左侧边界？

答：关键在于对于 nums[mid] == target 这种情况的处理：

    if (nums[mid] == target)
        right = mid;
1
2

可见，找到 target 时不要立即返回，而是缩小「搜索区间」的上界 right，在区间 [left, mid) 中继续搜索，即不断向左收缩，达到锁定左侧边界的目的。

int left_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    // 搜索区间为 [left, right]
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            // 搜索区间变为 [mid+1, right]
            left = mid + 1;
        } else if (nums[mid] > target) {
            // 搜索区间变为 [left, mid-1]
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 收缩右侧边界
            right = mid - 1;
        }
    }
    // 检查出界情况
    if (left >= nums.length || nums[left] != target) {
        return -1;
    }
    return left;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 寻找右侧边界的二分查找

左闭右开的写法

int right_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0, right = nums.length;
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            left = mid + 1; // 注意
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid;
        }
    }
    return left - 1; // 注意
}
int right_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 这里改成收缩左侧边界即可
            left = mid + 1;
        }
    }
    // 这里改为检查 right 越界的情况，见下图
    if (right < 0 || nums[right] != target) {
        return -1;
    }
    return 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

对于寻找左右边界的二分搜索，常见的手法是使用左闭右开的「搜索区间」，我们还根据逻辑将「搜索区间」全都统一成了两端都闭，便于记忆，只要修改两处即可变化出三种写法：

int binary_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) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1; 
        } else if(nums[mid] == target) {
            // 直接返回
            return mid;
        }
    }
    // 直接返回
    return -1;
}

int left_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 别返回，锁定左侧边界
            right = mid - 1;
        }
    }
    // 最后要检查 left 越界的情况
    if (left >= nums.length || nums[left] != target) {
        return -1;
    }
    return left;
}

int right_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 别返回，锁定右侧边界
            left = mid + 1;
        }
    }
    // 最后要检查 right 越界的情况
    if (right < 0 || nums[right] != target) {
        return -1;
    }
    return 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
51
52
53
54
55
56

# # (opens new window)153. 寻找旋转排序数组中的最小值(opens new window) (opens new window)

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到： 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2] 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7] 注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。
输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。
1
2
3
4
5
6

思路：

升序数组+旋转，仍然是部分有序，考虑用二分查找。

这种二分查找难就难在，arr[mid] 跟谁比。

我们的目的是：当进行一次比较时，一定能够确定答案在 mid 的某一侧。一次比较为 arr[mid] 跟谁比的问题。 一般的比较原则有：

  • 如果有目标值 target，那么直接让 arr[mid] 和 target 比较即可。
  • 如果没有目标值，一般可以考虑 端点

旋转数组，那最小值右侧的元素肯定都小于数组中的最后一个元素 nums[n-1]，左侧元素都大于 num[n-1]

public static int findMin(int[] nums) {
  int left = 0;
  int right = nums.length - 1;
  //左闭右开
  while (left < right) {
    int mid = left + (right - left) / 2;
    //疑问：为什么right = mid;而不是 right = mid-1;
    //解答：{4,5,1,2,3}，如果right = mid-1，则丢失了最小值1
    if (nums[mid] < nums[right]) {
      right = mid;
    } else {
      left = mid + 1;
    }
  }
  return nums[left];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

如果是求旋转数组中的最大值呢

public static int findMax(int[] nums) {
  int left = 0;
  int right = nums.length - 1;

  while (left < right) {
    int mid = left + (right - left) >> 1;

    //因为向下取整，left可能会等于mid，所以要考虑
    if (nums[left] < nums[right]) {
      return nums[right];
    }

    //[left,mid] 是递增的，最大值只会在[mid,right]中
    if (nums[left] < nums[mid]) {
      left = mid;
    } else {
      //[mid,right]递增，最大值只会在[left, mid-1]中
      right = mid - 1;
    }
  }
  return nums[left];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# # (opens new window)33. 搜索旋转排序数组(opens new window) (opens new window)

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

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

思路：

旋转数组后，依然是局部有序，从数组中间分成左右两部分后，一定有一部分是有序的

  • 如果 [l, mid - 1] 是有序数组，且 target 的大小满足 [{nums}[l],{nums}[mid]))，则我们应该将搜索范围缩小至 [l, mid - 1]，否则在 [mid + 1, r] 中寻找。
  • 如果 [mid, r] 是有序数组，且 target 的大小满足 ({nums}[mid+1],{nums}[r]]，则我们应该将搜索范围缩小至 [mid + 1, r]，否则在 [l, mid - 1] 中寻找。
public static int search(int[] nums,int target) {
  int n = nums.length;
  //特例
  if (n == 0) {
    return -1;
  }
  if (n == 1) {
    return nums[0] == target ? 0 : -1;
  }

  int left = 0;
  int right = nums.length - 1;

  while (left <= right) {
    int mid = left + (right - left) / 2;
    if (target == nums[mid]) {
      return mid;
    }
    //左侧有序的话
    if (nums[0] <= nums[mid]) {
      if (nums[0] <= 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 -1;
}
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

# # (opens new window)34. 在排序数组中查找元素的第一个和最后一个位置(opens new window) (opens new window)

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
1
2
3
4

思路：二分法寻找左右边界值

public int[] searchRange(int[] nums, int target) {
  int first = binarySearch(nums, target, true);
  int last = binarySearch(nums, target, false);
  return new int[]{first, last};
}

public int binarySearch(int[] nums, int target, boolean findLast) {
  int length = nums.length;
  int left = 0, right = length - 1;
  //结果，因为可能有多个值，所以需要先保存起来
  int index = -1;
  while (left <= right) {
    //取中间值
    int middle = left + (right - left) / 2;

    //找到相同的值（只有这个地方和普通二分查找有不同）
    if (nums[middle] == target) {
      //先赋值一下，肯定是找到了，只是不知道这个值是不是在区域的边界内
      index = middle;
      //如果是查找最后的
      if (findLast) {
        //那我们将浮标移动到下一个值试探一下后面的值还是否有target
        left = middle + 1;
      } else {
        //否则，就是查找第一个值，也是同理，移动指针到上一个值去试探一下上一个值是不是等于target
        right = middle - 1;
      }

      //下面2个就是普通的二分查找流程，大于小于都移动指针
    } else if (nums[middle] < target) {
      left = middle + 1;
    } else {
      right = middle - 1;
    }

  }
  return index;
}
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

# # (opens new window)287. 寻找重复数(opens new window) (opens new window)

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。

你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

输入：nums = [1,3,4,2,2]
输出：2
输入：nums = [3,1,3,4,2]
输出：3
1
2
3
4

思路：

二分查找的思路是先猜一个数（有效范围 [left..right] 里位于中间的数 mid），然后统计原始数组中 小于等于 mid 的元素的个数 cnt：

如果 cnt 严格大于 mid。根据抽屉原理，重复元素就在区间 [left..mid] 里； 否则，重复元素就在区间 [mid + 1..right] 里。 与绝大多数使用二分查找问题不同的是，这道题正着思考是容易的，即：思考哪边区间存在重复数是容易的，因为有抽屉原理做保证。

public int findDuplicate(int[] nums) {
  int len = nums.length;
  int left = 1;
  int right = len - 1;
  while (left < right) {
    int mid = left + (right - left) / 2;

    int cnt = 0;
    for (int num : nums) {
      if (num <= mid) {
        cnt += 1;
      }
    }

    // 根据抽屉原理，小于等于 4 的个数如果严格大于 4 个，此时重复元素一定出现在 [1..4] 区间里
    if (cnt > mid) {
      // 重复元素位于区间 [left..mid]
      right = mid;
    } else {
      // if 分析正确了以后，else 搜索的区间就是 if 的反面区间 [mid + 1..right]
      left = mid + 1;
    }
  }
  return left;
}
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

# # (opens new window)162. 寻找峰值(opens new window) (opens new window)

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞ 。

你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

输入：nums = [1,2,3,1]
输出：2
解释：3 是峰值元素，你的函数应该返回其索引 2。
输入：nums = [1,2,1,3,5,6,4]
输出：1 或 5 
解释：你的函数可以返回索引 1，其峰值元素为 2；
     或者返回索引 5， 其峰值元素为 6。
1
2
3
4
5
6
7

思路：

这题，最简单的思路就是直接找最大值，但这样复杂度是

在二分查找中，每次会找到一个位置 midmid。我们发现，midmid 只有如下三种情况：

  • midmid 为一个峰值，此时我们通过比较 midmid 位置元素与两边元素大小即可。
  • midmid 在一个峰值右侧，此时有 nums[mid] < nums[mid + 1]nums[mid]<nums[mid+1]，此时我们向右调整搜索范围，在 [mid + 1, r][mid+1,r] 范围内继续查找。
  • midmid 在一个峰值左侧，此时有 nums[mid] < nums[mid - 1]nums[mid]<nums[mid−1]，此时我们向左调整搜索范围，在 [l + 1, mid][l+1,mid] 范围内继续查找。
public int findPeakElement(int[] nums) {
  int n = nums.length;
  if (n == 1) {
    return 0;
  }

  // 先特判两边情况
  if (nums[0] > nums[1]) return 0;
  if (nums[n - 1] > nums[n - 2]) return n - 1;

  int l = 0, r = n - 1;
  while (l <= r) {
    int mid = (l + r) / 2;

    // 当前为峰值
    if (mid >= 1 && mid < n - 1 && nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1]) {
      return mid;
    } else if (mid >= 1 && nums[mid] < nums[mid - 1]) {
      // 峰值在 mid 左侧
      r = mid - 1;
    } else if (mid < n - 1 && nums[mid] < nums[mid + 1]) {
      // 峰值在 mid 右侧
      l = mid + 1;
    }
  }
  return -1;
}
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

# # (opens new window)240. 搜索二维矩阵 II(opens new window) (opens new window)

剑指 Offer 04. 二维数组中的查找 (opens new window) (opens new window)一样的题目

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

现有矩阵 matrix 如下：

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]
1
2
3
4
5
6
7

给定 target = 5，返回 true。

给定 target = 20，返回 false。

思路：

站在右上角看。这个矩阵其实就像是一个Binary Search Tree。然后，聪明的大家应该知道怎么做了。

public static boolean findNumberIn2DArray(int[][] matrix, int target) {

  if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
    return false;
  }

  int rows = matrix.length;
  int columns = matrix[0].length;
  for (int i = 0; i < rows; i++) {
    for (int j = 0; j < columns; j++) {
      if (matrix[i][j] == target) {
        return true;
      }
    }
  }
  return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

如果你写出这样的暴力解法，面试官可能就会反问你了：你还有什么想问的吗？

言归正传，有序的数组，我们首先应该想到二分

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        for (int[] row : matrix) {
            int index = search(row, target);
            if (index >= 0) {
                return true;
            }
        }
        return false;
    }

    public int search(int[] nums, int target) {
        int low = 0, high = nums.length - 1;
        while (low <= high) {
            int mid = (high - low) / 2 + low;
            int num = nums[mid];
            if (num == target) {
                return mid;
            } else if (num > target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return -1;
    }
}
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

Z 字形查找

假设arr数组，val，tar如下图所示： 如果我们把二分值定在右上角或者左下角，就可以进行二分。这里以右上角为例，左下角可自行分析： 图片说明 1）我么设初始值为右上角元素，arr[0][5] = val，目标tar = arr[3][1] 2）接下来进行二分操作： 3）如果val == target,直接返回 4）如果 tar > val, 说明target在更大的位置，val左边的元素显然都是 < val，间接 < tar，说明第 0 行都是无效的，所以val下移到arr[1][5] 5）如果 tar < val, 说明target在更小的位置，val下边的元素显然都是 > val，间接 > tar，说明第 5 列都是无效的，所以val左移到arr[0][4] 6）继续步骤2)

public static boolean findNumberIn2DArray(int[][] matrix, int target) {

  if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
    return false;
  }

  int rows = matrix.length;
  int columns = matrix[0].length;
  //右上角坐标
  int row = 0;
  int col = columns - 1;
  while (row < rows && col >= 0) {
    int num = matrix[row][col];
    if (num == target) {
      return true;
    } else if (target > num) {
      row++;
    } else {
      col--;
    }
  }
  return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
编辑 (opens new window)
上次更新: 2023/02/17, 17:03:51
排序
双指针

← 双指针→

最近更新
01
电商-商品系统设计
12-17
02
关于如何写OKR
12-09
03
对事不对人 vs 对人不对事
12-09
更多文章>
Theme by Vdoing | Copyright © 2022-2023 YoungAnnn | MIT License