【题解】二分查找-I、二维数组中的查找-Toy模板网

这篇具有很好参考价值的文章主要介绍了【题解】二分查找-I、二维数组中的查找。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

二分查找-I

题目链接：二分查找-I

解题思路：遍历

代码如下：文章来源地址https://www.toymoban.com/news/detail-633817.html

    int search(vector<int>& nums, int target) {
        for(int i=0; i<nums.size(); ++i){
            if(nums[i] == target) return i;
        }
        return -1;
    }

这种解题思路很明显没有很好的利用题目中强调的数组是升序的，既然是升序，那肯定前半部分偏小，后半部分偏大，如果我们能知道应该去前半部分还是后半部分寻找target，效率相对就提升很多了，于是我们有了下面的分治法

解题思路2：二分

二分就是采用了分而治之的思想，将大问题化为小问题求解

首先我们从数组首尾开始，每次取中点值
其次比较target和中点值的大小关系，如果中间值等于目标即找到了，可返回下标，如果target大于中点值，就代表着相等的值肯定不在左边，小于，就肯定不在右边，此时移动查找区间，重新定位中点值，重新比较
直到左右区间相遇，则证明没有找到，返回-1

代码如下：

    int search(vector<int>& nums, int target) {
        int l = 0;
        int r = nums.size()-1;
        while(l <= r){
            int m = (r + l) / 2;
            if(nums[m] == target){
                return m;
            }else if(nums[m] < target){
                l = m + 1;//进入右区间
            }else{
                r = m - 1;//进入左区间
            }
        }
        return -1;
    }

二维数组中的查找

题目链接：二维数组中的查找

解题思路：分治

代码如下：

    bool Find(int target, vector<vector<int> > array) {
        int r = 0, c = array[0].size()-1;
        while(r < array.size() && c >= 0){
            if(array[r][c] == target){
                return true;
            }else if(array[r][c] < target){
                r++;
            }else{
                c--;
            }
        }
        return false;
    }