当前位置：网站首页>Binary search

Binary search

2022-06-26 02:18:00 【51CTO】

One 、 Two points search

1. matrix

1.1 1351. Count the negative numbers in an ordered matrix

To give you one m * n Matrix grid, The elements of a matrix, whether by row or column , All in non increasing order . Please count and return grid in negative Number of .

Example 1：

Example 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. Search for a two-dimensional matrix

Write an efficient algorithm to judge m x n Matrix , Is there a target value . The matrix has the following characteristics ：

The integers in each row are arranged in ascending order from left to right .
The first integer in each row is greater than the last integer in the previous row .

Example 1：

Example 2：

Tips ：

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) {
        //  A two-dimensional   change   A one-dimensional 
        // 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. The weakest in the matrix K That's ok

Give you a size of m * n Matrix mat, The matrix consists of a number of soldiers and civilians , Use them separately 1 and 0 Express .

Please return to the weakest in the matrix k Index of rows , Sort by weakest to strongest .

If the first i The number of soldiers in line is less than the number of j That's ok , Or two lines of soldiers in the same number but i Less than j, So we think the i The battle effectiveness of the line is better than the first j Row weakness .

Soldiers Always The front position in a row , in other words 1 Always in 0 Before .

Example 1：

 Input ：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
 Output ：[2,0,3]
 explain ：
 The number of soldiers in each line ：
 That's ok  0 -> 2 
 That's ok  1 -> 4 
 That's ok  2 -> 1 
 That's ok  3 -> 2 
 That's ok  4 -> 5 
 Sort these rows from the weakest to the strongest to get  [2,0,3,1,4]

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

Example 2：

 Input ：mat = 
[[1,0,0,0],
 [1,1,1,1],
 [1,0,0,0],
 [1,0,0,0]], 
k = 2
 Output ：[0,2]
 explain ： 
 The number of soldiers in each line ：
 That's ok  0 -> 1 
 That's ok  1 -> 4 
 That's ok  2 -> 1 
 That's ok  3 -> 1 
 Sort these rows from the weakest to the strongest to get  [0,2,3,1]

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

Tips ：

m == mat.length
n == mat[i].length
2 <= n, m <= 100
1 <= k <= m
matrix[i] [j] No 0 Namely 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;
                }
            }
            //  Subscript 0  Express   Soldiers   Count  --  Subscript 1  Express   Indexes 
            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. Check the existence of integers and their multiples

Give you an array of integers arr, Please check whether there are two integers N and M, Satisfy N yes M Twice as many （ namely ,N = 2 * M）.

More formally , Check if there are two subscripts i and j Satisfy ：

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

Example 1：

Example 2：

Example 3：

Tips ：

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);
        //  Deal with negative numbers 
        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;
            }
        }
        //  Handle   Positive numbers 
        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.

Two 、 Conclusion

In the comment area, you can leave a message , Can be private , Can communicate and learn from each other , Common progress , You are welcome to give comments or comments , I am committed to high-quality articles .
Welcome to other excellent articles , I think it's great. You can put it away , Keep it for later use .
Personal blog Garden ： https://www.cnblogs.com/fyphome
Personal blog ： http://fyupeng.github.io/
Github Technical column ： github.com/Fyupeng