对于二分的疑惑🤔. 希望能够找个较为统一的写法.

Job Hunting Interview
1

我二分题也做了不少了。大体上看就两种写法比较主流.

  1. while (left < right) {/left 和 right重合, 而且经常left=mid+1, right = mid/}
  2. while (left + 1 < right) {/判断left, right对应的值, 经常left=mid+1, right=mid-1或者left=mid, right=mid/}
    当然有时候 while (left <= right) 也会出现，但是通常是为了解决最小单位 小于1的情况, 比如求一个数的root。

我比较疑惑的是法1和法2的取舍。比如说 leetcode 302. 如果我用while (left < right). 那么我就会在第二个二分的函数那写start = mid, right = mid-1. 但是这样会TLE, 当省最后两个值的时候就出不了循环。

var minArea = function(image, x, y) {
    const m = image.length, n = image[0].length;
    let left = searchLeft(0, y);
    let right= searchRight(y, n-1);
    let top =  searchTop(0, x);
    let bottom=searchBottom(x, m-1);
    
    return (right - left + 1) * (bottom - top + 1);
    
    function searchLeft(start, end) {
        while (start + 1 < end) {
            let mid = start + Math.floor((end-start)/2);
            if (isEmptyCol(mid)) {
                start = mid;
            } else end = mid;
        }
        if (isEmptyCol(start)) return end;
        return start;
    }
    
    function searchRight(start, end) {
        while (start + 1 < end) {
            let mid = start + Math.floor((end-start)/2);
            if (isEmptyCol(mid)) {
                end = mid;
            } else start = mid;
        }
        if (isEmptyCol(end)) return start;
        return end;
    }
    
    function searchTop(start, end) {
        while (start + 1 < end) {
            let mid = start + Math.floor((end-start)/2);
            if (isEmptyRow(mid)) {
                start = mid;
            } else end = mid;
        }
        if (isEmptyRow(start)) return end;
        return start;
    }
    
    function searchBottom(start, end) {
        while (start + 1 < end) {
            let mid = start + Math.floor((end-start)/2);
            if (isEmptyRow(mid)) {
                end = mid;
            } else start = mid;
        }
        if (isEmptyRow(end)) return start;
        return end;
    }
    
    function isEmptyCol(col) {
        for (let i = 0; i < m; i++) {
            if (image[i][col] === '1') return false;
        }
        return true;
    }
    
    function isEmptyRow(row) {
        for (let i = 0; i < n; i++) {
            if (image[row][i] === '1') return false;
        }
        return true;
    }
};
2

也跟个人习惯有关。我几乎没有用过2 。
我的操作一般是：
a. while (left < right) {/ lleft=mid, right = mid /}
b. while (left <= right) {/ left=mid + 1, right = mid - 1 /}

3

我一次过二分题的概率好低:joy:. 一定要总结出来

4

个人不喜欢用 start + 1 < end ， 我看你 LC 302 Smallest Rectangle Enclosing Black Pixels 用的也是这个

帖下题目：

An image is represented by a binary matrix with 0 as a white pixel and 1 as a black pixel. The black pixels are connected, i.e., there is only one black region. Pixels are connected horizontally and vertically. Given the location (x, y) of one of the black pixels, return the area of the smallest (axis-aligned) rectangle that encloses all black pixels.

Example:

Input:
[
“0010”,
“0110”,
“0100”
]
and x = 0, y = 2

Output: 6

也可以参考

https://blog.csdn.net/jmspan/article/details/51187166

https://blog.csdn.net/magicbean2/article/details/75347242

Binary Search

Intuition

Project the 2D image into a 1D array and use binary search to find the boundaries.

Algorithm

matrix projection

image
image.png564×503 34.7 KB

*Figure 1. Illustration of image projection.

Suppose we have a 10 \times 1110×11 image as shown in figure 1, if we project each column of the image into an entry of row vector v with the following rule:

v[i] = 1 if exists x such that image[x][i] = 1
v[i] = 0 otherwise
That is

If a column has any black pixel it’s projection is black otherwise white.

Similarly, we can do the same for the rows, and project the image into a 1D column vector. The two projected vectors are shown in figure 1.

Now, we claim the following lemma:

Lemma

If there are only one black pixel region, then in a projected 1D array all the black pixels are connected.

Proof by contradiction

Assume to the contrary that there are disconnected black pixels at i and j where i < j in the 1D projection array. Thus, there exists one column k, k in (i, j) and the column k in the 2D array has no black pixel. Therefore, in the 2D array there exist at least two black pixel regions separated by column k which contradicting the condition of “only one black pixel region”. Therefore, we conclude that all the black pixels in the 1D projection array are connected.

With this lemma, we have the following algorithm:

Project the 2D array into a column array and a row array
Binary search to find left in the row array within [0, y)
Binary search to find right in the row array within [y + 1, n)
Binary search to find top in the column array within [0, x)
Binary search to find bottom in the column array within [x + 1, m)
Return (right - left) * (bottom - top)
However, the projection step cost O(mn) time which dominates the entire algorithm.If so, we gain nothing comparing with previous approaches.

The trick is that we do not need to do the projection step as a preprocess. We can do it on the fly, i.e. “don’t project the column/row unless needed”.

Recall the binary search algorithm in a 1D array, each time we only check one element, the pivot, to decide which half we go next.

In a 2D array, we can do something similar. The only difference here is that the element is not a number but a vector. For example, a m by n matrix can be seen as n column vectors.

In these n elements/vectors, we do a binary search to find left or right. Each time we only check one element/vector, the pivot, to decide which half we go next. In total it checks O(\log n)O(logn) vectors, and each check is O(m)O(m) (we simply traverse all the m entries of the pivot vector).

So it costs O(mlogn) to find left and right. Similarly it costs O(nlogm) to find top and bottom. The entire algorithm has a time complexity of O(mlogn+nlogm)

public class Solution {
    public int minArea(char[][] image, int x, int y) {
        int m = image.length, n = image[0].length;
        int left = searchColumns(image, 0, y, 0, m, true);
        int right = searchColumns(image, y + 1, n, 0, m, false);
        int top = searchRows(image, 0, x, left, right, true);
        int bottom = searchRows(image, x + 1, m, left, right, false);
        return (right - left) * (bottom - top);
    }
    private int searchColumns(char[][] image, int i, int j, int top, int bottom, boolean whiteToBlack) {
        while (i != j) {
            int k = top, mid = (i + j) / 2;
            while (k < bottom && image[k][mid] == '0') ++k;
            if (k < bottom == whiteToBlack) // k < bottom means the column mid has black pixel
                j = mid; //search the boundary in the smaller half
            else
                i = mid + 1; //search the boundary in the greater half
        }
        return i;
    }
    private int searchRows(char[][] image, int i, int j, int left, int right, boolean whiteToBlack) {
        while (i != j) {
            int k = left, mid = (i + j) / 2;
            while (k < right && image[mid][k] == '0') ++k;
            if (k < right == whiteToBlack) // k < right means the row mid has black pixel
                j = mid;
            else
                i = mid + 1;
        }
        return i;
    }
}

Complexity Analysis

Time complexity : O(mlogn+nlogm).
Here, mm and nn are the height and width of the image. We embedded a linear search for every iteration of binary search. See previous sections for details.

Space complexity : O(1).
Both binary search and linear search used only constant extra space.

5

这题跟FB的高频题 find left most one in matrix 几乎是一个做法

6

这篇文章也许对你有用