74. Search a 2D Matrix

Write an efficient algorithm that searches for a value in an mxn matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

For example,

Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target=3, returntrue.

S: Binary search O(lognm)

2d matrix to 1d sorted array

    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        if (m == 0) return false;
        int n = matrix[0].size();
        if (n == 0) return false;
        int left = 0, right = m * n - 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            int x = mid / n, y = mid % n;
            if (matrix[x][y] == target) return true;
            if (matrix[x][y] < target) left = mid;
            else right = mid;
        }
        int x = left / n, y = left % n;
        int x1 = right / n, y1 = right % n;
        return matrix[x][y] == target || matrix[x1][y1] == target;
    }

240. Search a 2D Matrix II

Write an efficient algorithm that searches for a value in anmxnmatrix. This matrix has the following properties:

• Integers in each row are sorted in ascending from left to right.
• Integers in each column are sorted in ascending from top to bottom.

For example,

Consider the following 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]
]

Given target=5, returntrue.

Given target=20, returnfalse.

S1: binary search O(m + n)

观察matrix规律，找到可以排除元素的关键点：右上角点

若右上角点<target可以排除该行，若右上角点 > target可以排除该列

    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        if (m == 0) return false;
        int n = matrix[0].size();
        int x = 0, y = n - 1;
        while (x < m && y >= 0) {
            if (matrix[x][y] == target) return true;
            if (matrix[x][y] < target) {
                x++;
            } else {
                y--;
            }
        }
        return false;
    }

S2: binary search O(log(mn))

将matrix划分为四份，每次排除两份

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        m = matrix.size();
        if (m == 0) return false;
        n = matrix[0].size();
        return binarySearch(matrix, 0, 0, m - 1, n - 1, target);
    }

    bool binarySearch(vector<vector<int>>& matrix, int x1, int y1, int x2, int y2, int target) {
        if (!valid(x1, y1) || !valid(x2, y2) || x1 > x2 || y1 > y2) return false;
        int midx = x1 + (x2 - x1) / 2, midy = y1 + (y2 - y1) / 2;
        if (matrix[midx][midy] == target) return true;
        if (matrix[midx][midy] > target) {
            while (matrix[midx][midy] > target && valid(midx - 1, midy - 1)) {
                midx--;
                midy--;
            }            
        } else {
            while (matrix[midx][midy] < target && valid(midx + 1, midy + 1)) {
                midx++;
                midy++;
            }
        }
        if (matrix[midx][midy] == target) return true;
        if (matrix[midx][midy] < target) {
            return binarySearch(matrix, x1, midy + 1, midx, y2, target) || 
                   binarySearch(matrix, midx + 1, y1, x2, midy, target);
        } else {
            return binarySearch(matrix, x1, midy, midx - 1, y2, target) || 
                   binarySearch(matrix, midx, y1, x2, midy - 1, target);
        }
    }

    bool valid(int x, int y) {
        return x >= 0 && x < m && y >= 0 && y < n;
    }

private:
    int m, n;
};

35. Search Insert Position

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

S: binary search O(logn)

注意当target要插入所有元素之后的corner case

    int searchInsert(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return mid;
            if (nums[mid] < target) left = mid;
            else right = mid;
        }
        if (nums[left] == target) return left;
        if (nums[right] == target) return right;
        return nums[left] > target? left : nums[right] > target? right : right + 1;
    }