矩阵查找

本篇内容虽多，但有助于系统构建对二分查找的知识体系，如果您还不能闭着眼睛写二分的话，建议仔细看看哦～

二分查找是一个思路很简单、但实现起来有点恼人的算法。正所谓知己知彼，胜乃不怠；知天知地，胜乃不穷，我们先对二分法这个“敌人”做一个简单的分类：

1. 按查找区间分类——闭区间[..]和左闭右开区间[..)
2. 按具体任务分类——寻找特定值、寻找左侧边界和寻找右侧边界

寻找特定值

给定一个有序数组，如[1, 2, 5, 8, 9, 13, 19, 20, 68]，查找19的位置：

int binarySearch(vector<int> array, int target) {
    int left = 0, right = array.size() - 1;  // ☢︎☢︎☢︎

    while (left <= right) {                  // ☢︎☢︎☢︎
        int mid = left + (right-left)/2;     // ☢︎☢︎☢︎
        if (array[mid] < target) left = mid + 1;
        else if (array[mid] > target) right = mid - 1;
        else if (array[mid] == target) return mid;
    }

    return -1;
}

框架的☢︎☢︎☢︎部分是尤其需要我们注意的，这里我们选取的是在闭区间[..]内查找，因此right=array.size()-1，且循环条件为left <= right；另外的话mid = left + (right-left)/2，这么写比mid = (left+right)/2要好，可以防止left+right溢出。

如果您想在开区间内查找，这么改即可：右侧端点变成right = array.size()、循环条件变为left < right

寻找左侧边界

给定数组[1, 3, 5, 6, 6, 6, 8, 7]，找出6的左侧边界：

int binarySearch(vector<int> array, int target) {
    if (array.size() < 1) return -1;

    int left = 0, right = array.size() - 1;
    while (left <= right) {
        int mid = left + (right-left) / 2;
        if (array[mid] > target) right = mid - 1;
        else if (array[mid] < target) left = mid + 1;
        else if (array[mid] == target) right = mid - 1; // ☢︎☢︎☢︎
    }

    // ☢︎☢︎☢︎
    if (left >= array.size() || array[left] != target) return -1;
    else return left;
}

总体上和二分法寻找特定值一致，但是注意标记了☢︎☢︎☢︎的部分：

1. 当array[mid] == target，我们需要设置right = mid - 1
2. 循环结束后，需要判断left是否越过右边界，或者left位置对应的值不等于target

如果问题是寻找右侧边界，我们只需要在寻找左侧边界基础上改改即可：①当array[mid] == target时，设置left = mid + 1; ②循环结束后，判断right是否越过左边界，或者right位置对应的值不等于target.

本题思路与代码

用两次二分法，第一次定位所在行，第二次定位所在列，代码如下：

//
// Created by jt on 2020/9/3.
//
#include <vector>
using namespace std;

class Solution {
public:
    /**
     *
     * @param matrix int整型vector<vector<>>
     * @param target int整型
     * @return bool布尔型
     */
    bool searchMatrix(vector<vector<int> >& matrix, int target) {
        // write code here
        if (matrix.size() < 1 || matrix[0].size() < 1) return false;
        int row = matrix.size(), col = matrix[0].size();
        // 第一步：定位所在行
        int left = 0, right = row - 1, midRow;
        while (left <= right) {
            midRow = left + (right-left) / 2;
            if (matrix[midRow][0] > target)  right = midRow - 1;
            else if (matrix[midRow][col-1] < target) left = midRow + 1;
            else if (matrix[midRow][0] == target || matrix[midRow][col-1] == target) return true;
            else if (matrix[midRow][0] < target && matrix[midRow][col-1] > target) break;
        }
        if (left > right) return false; // 越界
        left = 0, right = col - 1;
        int midCol;
        // 第二步：定位所在列
        while (left <= right) {
            midCol = left + (right-left) / 2;
            if (matrix[midRow][midCol] > target) right = midCol - 1;
            else if (matrix[midRow][midCol] < target) left = midCol + 1;
            else if (matrix[midRow][midCol] == target) return true;
        }
        return false;
    }
};