力扣网C语言编程题：搜索二维矩阵的普通解法与二分查找法

一. 简介

本文记录力扣网上题目，涉及数组，双指针的逻辑题：在二维矩阵中搜索某个元素值。

二. 力扣网C语言编程题：搜索二维矩阵

题目：搜索二维矩阵

给你一个满足下述两条属性的 m x n 整数矩阵：
    每行中的整数从左到右按非严格递增顺序排列。
    每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

示例 1：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true

示例 2：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false

提示：
    m == matrix.length
    n == matrix[i].length
    1 <= m, n <= 100
    -104 <= matrix[i][j], target <= 104

解题思路一：（直接查找）

第一直觉可以直接在二维数组中进行查找的方法，不过这种方法的时间复杂度为O(n*n)，比较高。空间复杂度为 O(1)；

C语言实现如下：

//暴力解法
bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target) {
    int i,j;
    bool result = false;
    
    //matrixSize为二维数组的行
    for(i = 0; i < matrixSize; i++) {
        //(*matrixColSize)为二维数组的列
        for(j = 0; j < (*matrixColSize); j++) {
            if(matrix[i][j] == target) {
                result = true;
                break;
            }
        }
    }
    return result;
}

解题思路二：（二分查找法）

根据题目说明，每行元素递增，每行首元素小于上一行的最后一个元素，也就是说，可以把这个二维矩阵看作一维数组，使用二分查找法查找元素。

如果二维矩阵有m行，n列；

总共有元素个数：m*n-1；

对任意一个一维数组的索引 index，它在二维数组中的位置为：

行号：index / n

列号：index % n

C语言实现如下：

//二分查找法
bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target) {
    if (matrixSize == 0 || matrixColSize[0] == 0) {
        return false;
    }

    int m = matrixSize; //行数
    int n = matrixColSize[0]; //每个元素代表对应行的列数(假设每列元素个数一样)
    int left = 0;
    int right = m*n-1;
    int mid = 0;

    while(left <= right) {
        mid = (left + right) / 2;
        int r_index = mid / n;
        int c_index = mid % n;
        //matrix[r_index][c_index] 也就是对应一维数组的nums[mid]
        int element = matrix[r_index][c_index];
        if(element == target) {
            return true;
        }
        //element < target,说明 target在数组的右边,选右半区间
        else if(element < target) {
            left = mid + 1;
        }
        else {//element > target,说明target在数组左边，选左半边区间
            right = mid - 1;
        }
    }
    return false;
}

可以看出，二分查找法每一次迭代查找时区间都会取区间的一半，所以时间复杂度为 O(logn)。