当前位置：网站首页>二分查找

二分查找

2022-06-26 00:39:00 【51CTO】

一、二分查找

1. 矩阵

1.1 1351. 统计有序矩阵中的负数

给你一个 m * n 的矩阵 grid，矩阵中的元素无论是按行还是按列，都以非递增顺序排列。请你统计并返回 grid 中负数的数目。

示例1：

示例2：

class Solution {
    public int countNegatives(int[][] grid) {
        int count = 0;
        for(int i = 0 ; i < grid.length; i++) {
            count += countRowNegatives(grid[i]);
        }
        return count;
    }
    private int countRowNegatives(int[] row) {
        int left = 0;
        int right = row.length;
        while(left < right) {
            int mid = left + (right - left) / 2;
            if(row[mid] >= 0) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return row.length - 1 - left + 1;
    }
}

     1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.

1.2 74. 搜索二维矩阵

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。

示例1：

示例2：

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-104 <= matrix[i] [j], target <= 104

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        // 二维 变 一维
        // col + row = res
        // 1 * 4 + 1 = 5 -- 5 / 4 = 1 -- 5 % 4 = 1
        int left = 0;
        int col = matrix[0].length;
        int row = matrix.length;
        int right = row * col;
        while(left < right) {
            int mid = left + (right - left) / 2;
            if(matrix[mid / col][mid % col] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        if(left < row * col && target == matrix[left / col][left % col]) {
            return true;
        }
        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.

1.3 1337. 矩阵中战斗力最弱的 K 行

给你一个大小为 m * n 的矩阵 mat，矩阵由若干军人和平民组成，分别用 1 和 0 表示。

请你返回矩阵中战斗力最弱的 k 行的索引，按从最弱到最强排序。

如果第 i 行的军人数量少于第 j 行，或者两行军人数量相同但 i 小于 j，那么我们认为第 i 行的战斗力比第 j 行弱。

军人总是排在一行中的靠前位置，也就是说 1 总是出现在 0 之前。

示例1：

输入：mat = 
[[1,1,0,0,0],
 [1,1,1,1,0],
 [1,0,0,0,0],
 [1,1,0,0,0],
 [1,1,1,1,1]], 
k = 3
输出：[2,0,3]
解释：
每行中的军人数目：
行 0 -> 2 
行 1 -> 4 
行 2 -> 1 
行 3 -> 2 
行 4 -> 5 
从最弱到最强对这些行排序后得到 [2,0,3,1,4]

     
      1.
      2.
      3.
      4.
      5.
      6.
      7.
      8.
      9.
      10.
      11.
      12.
      13.
      14.
      15.
      16.

示例2：

输入：mat = 
[[1,0,0,0],
 [1,1,1,1],
 [1,0,0,0],
 [1,0,0,0]], 
k = 2
输出：[0,2]
解释： 
每行中的军人数目：
行 0 -> 1 
行 1 -> 4 
行 2 -> 1 
行 3 -> 1 
从最弱到最强对这些行排序后得到 [0,2,3,1]

     
      1.
      2.
      3.
      4.
      5.
      6.
      7.
      8.
      9.
      10.
      11.
      12.
      13.
      14.

提示：

m == mat.length
n == mat[i].length
2 <= n, m <= 100
1 <= k <= m
matrix[i] [j] 不是 0 就是 1

class Solution {
    public int[] kWeakestRows(int[][] mat, int k) {
        List<int[]> list = new ArrayList<>();
        for(int i = 0; i < mat.length; i++) {
            int left = 0;
            int right = mat[i].length;
            while(left < right) {
                int mid = left + (right - left) / 2;
                if(mat[i][mid] == 1) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            // 下标0 表示 军人 数 -- 下标1 表示 索引
            list.add(new int[]{left, i});
        }
        PriorityQueue<int[]> heap = new PriorityQueue(new Comparator <int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0] != o2[0]) {
                    return o1[0] - o2[0];
                } else {
                    return o1[1] - o2[1];
                }
            }
        });
        for(int i = 0; i < list.size(); i++) {
            heap.offer(list.get(i));
        }
        int[] res = new int[k];
        for(int i = 0; i < k; i++) {
            res[i] = heap.poll()[1];
        }
        return res;
    }
}

     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.

1.4 1346. 检查整数及其两倍数是否存在

给你一个整数数组 arr，请你检查是否存在两个整数 N 和 M，满足 N 是 M 的两倍（即，N = 2 * M）。

更正式地，检查是否存在两个下标 i 和 j 满足：

i != j
0 <= i, j < arr.length
arr[i] == 2 * arr[j]

示例1：

示例2：

示例3：

提示：

2 <= arr.length <= 500
-10^3 <= arr[i] <= 10^3

class Solution {
    public boolean checkIfExist(int[] arr) {
        Arrays.sort(arr);
        int poAndNaLine = binarySearch(arr, 0, arr.length, 0);
        // 处理负数
        for(int i = poAndNaLine - 1; i >= 0; i--) {
            int res = binarySearch(arr, 0, i, arr[i] * 2);
            if(res < arr.length && arr[res] == arr[i] * 2) {
                return true;
            }
        }
        // 处理 正数
        for(int i = poAndNaLine; i < arr.length; i++) {
            int res = binarySearch(arr, i + 1, arr.length, arr[i] * 2);
            if(res < arr.length && arr[res] == arr[i] * 2) {
                return true;
            }
        }
        return false;
    }
    private int binarySearch(int[] arr, int left, int right, int target) {
        while(left < right) {
            int mid = left + (right - left) / 2;
            if(arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        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.
26.
27.
28.
29.
30.
31.
32.

二、结束语

评论区可留言，可私信，可互相交流学习，共同进步，欢迎各位给出意见或评价，本人致力于做到优质文章。
欢迎参观其他优质文章，觉得很赞不妨收藏起来，留着以后用。
个人博客园： https://www.cnblogs.com/fyphome
个人博客： http://fyupeng.github.io/
Github技术专栏： github.com/Fyupeng