算法之旅008 - 二分搜索Level1 Day8

跟着LeetCode的Study Plan重温一遍各种经典算法，本期是二分搜索算法Level1 Day8。

题目构成：Easy*1 + Medium*1。

1351. Count Negative Numbers in a Sorted Matrix

二维数组，每行每列都是有序非递增的，统计负数的个数，代码(Golang)如下：

    func countNegatives(grid [][]int) int {

        m := len(grid)
        n := len(grid[0])

        // find negative number counts
        helper := func(_row []int) int {
            _i, _j := 0, len(_row)-1

            for _i <= _j {
                _m := (_i + _j) / 2
                _v := _row[_m]
                if _v >= 0 {
                    _i = _m + 1
                } else {
                    _j = _m - 1
                }
            }
            return len(_row) - _j - 1
        }

        neg_counts := make([]int, m)
        for i, row := range grid {

            if i == 0 {
                neg_counts[0] = helper(row)
            } else {
                last_neg_count := neg_counts[i-1]
                neg_counts[i] = last_neg_count + helper(row[:n-last_neg_count])
            }
        }
        r := 0
        for _, c := range neg_counts {
            r += c
        }
        return r
    }

这道题最合适的方式更简单，且时间复杂度是O(m+n)的，但这里还是用二分的思想去做的：
1. 使用二分法查找每行负数的个数
2. 进一步优化，如果上一行最后last_neg_count个元素是负数，这一行只需要搜索row[:n-last_neg_count]即可

74. Search a 2D Matrix

二维数组，每一行都是有序递增的，且下一行最小值大于上一行最大值，代码(Golang)如下：

    func searchMatrix(matrix [][]int, target int) bool {
        m := len(matrix)
        n := len(matrix[0])

        if matrix[0][0] > target || matrix[m-1][n-1] < target {
            return false
        }

        // step1: find the first row that the last element larger than or euqal to target
        i, j := 0, m-1
        target_row := -1
        for i <= j {
            k := (i + j) / 2
            v := matrix[k][n-1]
            if v == target {
                target_row = k
                break
            }
            if v > target {
                j = k - 1
            } else {
                i = k + 1
            }
        }
        if target_row == -1 {
            target_row = j + 1
        }

        // step2: find target in target row
        i, j = 0, n-1
        for i <= j {
            k := (i + j) / 2
            v := matrix[target_row][k]
            if v == target {
                return true
            }
            if v > target {
                j = k - 1
            } else {
                i = k + 1
            }
        }
        return false
    }

用两次二分，第一次找到目标值如果在二维数组中应该会在哪一行，第二次在这一行找目标值是否存在。