[LeetCode] 74 Search a 2D Matrix（二分查找）

fengziwei 2017-12-06 原文

二分查找

1.二分查找的时间复杂度分析：

二分查找每次排除掉一半不合适的值，所以对于n个元素的情况来说:

一次二分剩下：n/2

两次：n/4

m次：n/(2^m)

最坏情况是排除到最后一个值之后得到结果，所以：
n/(2^m) = 1

2^m = n

所以时间复杂度为：log2(n)

2.二分查找的实现方法：

（1）递归

int RecursiveBinSearch(int arr[], int bottom, int top, int key) {
    if (bottom <= top) {
        int mid = (bottom + top) / 2;
        if (arr[mid] == key) {
            return mid;
        } 
        else if (key < arr[mid]) {
            return RecursiveBinSearch(arr, bottom, mid - 1, key);
        }
        else {
            return RecursiveBinSearch(arr, mid + 1, top, key);
        }
    }
    else {
        return -1;
    }
}

（2）非递归

int nonRecursiveBinSearch(int arr[], int size, int key) {
    int bottom = 0, top = size - 1, mid;
    while (bottom <= top) {
        mid = (bottom + top) / 2;
        if (arr[mid] == key) {
            return mid;
        }
        else if (key < arr[mid]) {
            top = mid - 1;
        }
        else {
            bottom = mid + 1;
        }
    }
    return -1;
}

3.LeetCode题目：74 Search a 2D Matrix

原题地址：
https://leetcode.com/problems/search-a-2d-matrix/description/

题目：

解法：

这道题给出一个二维数组（已排序），再给定一个数，让我们确定这个数是否在这个二维数组里面。由于这个二维数组是排好序的，因此我们可以使用两次二分查找，第一次使用先定位好这个数在第几行，第二次使用确定这个数在第几列。

代码如下：

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.size() == 0 || matrix[0].size() == 0) return false;
        int col = getCol(matrix, 0, matrix.size() - 1, target);
        if (col == -1) {
            return false;
        }
        else {
            return isExist(matrix, col, 0, matrix[col].size() - 1, target);   
        }
    }
    int getCol(vector<vector<int>>& matrix, int first, int last, int target) {
        if (first > last) return -1;
        int mid = (first + last) / 2;
        if (matrix[mid][0] <= target && target <= matrix[mid][matrix[mid].size() - 1]) {
            return mid;
        }
        else {
            if (target < matrix[mid][0]) {
                return getCol(matrix, first, mid - 1, target);
            }
            else {
                return getCol(matrix, mid + 1, last, target);
            }
        }
    }
    bool isExist(vector<vector<int>>& matrix, int col, int first, int last, int target) {
        if (first > last) {
            return false;
        }
        else {
            int mid = (first + last) / 2;
            if (matrix[col][mid] == target) {
                return true;
            }
            else {
                if (matrix[col][mid] > target) {
                    return isExist(matrix, col, first, mid - 1, target);
                }
                else {
                    return isExist(matrix, col, mid + 1, last, target);
                }
            }
        }
    }
};

后来出于好奇直接用两层循环来查找，最后所花的时间竟然和用二分查找一样，哎：

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        for (int i = 0; i < matrix.size(); i++) {
            for (int j = 0; j < matrix[i].size(); j++) {
                if (matrix[i][j] == target) return true;
            }
        }
        return false;
    }
};