算法笔记_面试题_17.二分法搜索_模板及示例

谁践踏了优雅 2022-08-28 03:59 104阅读 0赞

**目录**

1. 二分法搜索简介及模板

例1. 在升序数组中，找第一次出现target对象的索引

2. 求开根号 sqrt(x)

例2. int sqrt( int x) 求整数的开方

例3. double sqrt (doube x) 求浮点型数值的开方

3. 二维矩阵中找target

例4. 严格递增矩阵中，查找target

例5. 非严格递增二维矩阵中找target.

--------------------

# 1. 二分法搜索简介及模板 #

参考：[九章算法][Link 1]

**通常什么时候会用到二分法？**

*  当一个搜索问题可以使用for循环进行O(n)时间复杂度搜索，为了优化到O(logN)级别时，通常会用到二分搜索法。
    
     *  出现 sorted 字眼时，即已排序的集合时。

**模板如例1所示：**

*  **核心思想：** 不断的缩小搜索范围！不是想着一下子找到target, 而是想着怎么样**缩小范围到2个数**！
    
     *  O(n) ->O(n/2)->O(n/4)->...O(1)
 *  **本质： 找满足某个条件的 最后一个 或 第一个 位置**
    
     *  **再深层的本质：保留有答案的一边，没有答案的一边不要。。**
     *  **再再深层的本质：每次留下一半！不断缩小搜索范围**
     *  ![e09fce574de446218de85d40b3f2c6fa.png][]

## 例1. **[在升序数组中，找第一次出现target对象的索引][target]** ##

**描述：**

给定一个排序的整数数组（升序）和一个要查找的整数 `target`，用O(logn)O(logn)的时间查找到`target`**第一次出现的下标**（从`0`开始），如果`target`不存在于数组中，返回`-1`。

输入：

数组 = [1, 2, 3, 3, 4, 5, 10]
    target = 3

输出：2

**模板代码：**

class Solution {
    public:
        /**
         * @param nums: The integer array.
         * @param target: Target to find.
         * @return: The first position of target. Position starts from 0.
         */
        int binarySearch(vector<int> &nums, int target) {
            if (nums.size() == 0) { //string有size()也有length(), vector只有size()
                return -1;
            }
    
            int start = 0;
            int end = nums.size() - 1;
            while (start + 1 < end) {                 //注意: 这里是start+1, while只是为了将搜索范围减小到相邻的2个元素即可！
                int mid = start + (end - start) / 2;  //注意：这里不是(start+end)/2, 防止(start+end)太大，导致越界！更不是 (start - end) / 2
                if (nums[mid] == target) {
                    end = mid;           //模板变化部分，如 last positon: start = mid; 后面 if 颠倒位置； 又如：any position: 这里直接 return mid;
                } else if (nums[mid] < target) {
                    start = mid;
                } else {
                    end = mid;
                }
            }
            if (nums[start] == target) { //模板变化部分(如变化两个if前后顺序)
                return start;
            } 
            if (nums[end] == target) {
                return end;
            }
    
            return -1;
        }
    };

**拓展：**

*  last position: lintcode [458 · 目标最后位置][458 _]
 *  any position: leecode

**Tips: 递归**recursion**与while-loop**

工程开发中：我们尽量避免recursion, 因为很占栈空间！！！而系统一般给程序分配很少的栈空间，比如8M大小。对于搜索问题，一般可以用recursion, 对于二叉树的前中序遍历，递归太简单，一般面试官会考recursion.

# 2. 求开根号 sqrt(x) #

## [例2. int sqrt( int x) 求整数的开方][2. int sqrt_ int x_] ##

**int mySqrt(int x) \{ \}**

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x \*\* 0.5 。

示例 1：

> 输入：x = 4  
> 输出：2

示例 2：

> 输入：x = 8  
> 输出：2  
> 解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

等价于 求 最大的一个整数num， 使num^2 <= x. (**last position问题**)

class Solution {
    public:
        int mySqrt(int x) {
            if (x <= 0)
                return 0;
            int start = 0;
            int end = x;
            while (start + 1 < end) {
                int mid = start + (end -start) / 2;
                long long num = (long long) mid * mid; //注意：这里要做强制转化！！！！
                if (num == x) {
                    start = mid; //return mid; //这两句均可
                } else if (num < x) {
                    start = mid;
                } else {
                    end = mid;
                }
            }
            if ((long long)end * end <= x) {        //注意：这里要有等于号！这里要做强制转化！！！！
                return end;
            }
            if ((long long)start * start <= x) {    //注意：这里要有等于号！这里要做强制转化！！！！
                return start;
            }
    
            return 0;
        }
    };

## 例3. [double sqrt (doube x) 求浮点型数值的开方][double sqrt _doube x_] ##

对应[ lintcode 586 · 对x开根II][double sqrt _doube x_]

**描述：**

实现 `double sqrt(double x)` 并且 `x >= 0`。计算并返回x开根后的值。精确度保持在小数点后12位。

例1:

输入: n = 2 
    输出: 1.41421356

例2:

输入: n = 3
    输出: 1.73205081

**代码：**

**区别：这里的逻辑不再是找两个相邻的，而是找两个相等的数！**

class Solution {
    public:
        /**
         * @param x: a double
         * @return: the square root of x
         */
        double PRECISION = 1e-10;
        double sqrt(double x) {
            double start = 0;
            double end   = x;
            if (x < 1) { //注意：这里 < 1的数值x，上节应该是1
                end = 1;
            }
    
            while (end - start > PRECISION) {   //特别注意: 这里不是+1了，也不是 start<end (会超时！)
                double mid = start + (end - start) / 2 ;
                double num = mid * mid;
                if (num < x) {                 //注意：这里的逻辑不再是找两个相邻的，而是找两个相等的数！//这里不要使用 abs(num-x)<1e-10,计算结果不是"最大"的result^2 < x
                    start = mid; 
                } else {
                    end = mid;
                }
            }
    
            return start; // 等价于 return end;
        }
    };

# 3. 二维矩阵中找target #

## 例4. 严格递增矩阵中，查找target ##

**描述**

写出一个高效的算法来搜索 `m × n`矩阵中的值 `target` 。

这个矩阵具有以下特性：

*  每行中的整数从左到右是排序的。
 *  每行的第一个数大于上一行的最后一个整数。

**样例 1：**

输入：

矩阵 = [[5]]
    target = 2

输出：

false

解释：矩阵中没有包含2，返回false。

**样例 2：**

输入：

[https://www.lintcode.com/problem/28/][https_www.lintcode.com_problem_28]

输出：

true

解释：矩阵中包含3，返回true。

**代码：**

**思想：**严格递增的二维数组，其实可以当做是一维数组看待，只不过，遍历时**，一维数组的array \[index\], 对应的matrix中的matrix\[index/col\]\[index%col\],** 其他等同于从一维数组中找target.

class Solution {
    public:
        /**
         * @param matrix: matrix, a list of lists of integers
         * @param target: An integer
         * @return: a boolean, indicate whether matrix contains target
         */
        bool searchMatrix(vector<vector<int>> &matrix, int target) {
            // write your code here
            if (matrix.empty()) {
                return false;
            }
    
            int start = 0;
            int row = matrix.size();
            int col = matrix[0].size();
            int end = row * col - 1; //注意： 这里作为索引，要减 1
            while (start + 1 < end) {
                int mid = start + (end - start) / 2;
                if (matrix[mid/col][mid%col] == target) { //注意：取矩阵元素的方式！
                    return true;
                } else if (matrix[mid/col][mid%col] < target) {
                    start = mid;
                } else {
                    end = mid;
                }
            }
            if (matrix[start/col][start%col] == target) {
                return true;
            }
            if (matrix[end/col][end%col] == target) {
                return true;
            }
    
            return false;
        }
    };

## 例5. 非严格递增二维矩阵中找target. ##

[LintCode 领扣][LintCode]

[力扣][Link 2] = [力扣][Link 3]

[Link 1]: https://www.jiuzhang.com/solutions/binary-search/
[e09fce574de446218de85d40b3f2c6fa.png]: /images/20220828/e1321abeed15401181ae0b45ea018f6f.png
[target]: https://www.lintcode.com/problem/14/
[458 _]: https://www.lintcode.com/problem/458/
[2. int sqrt_ int x_]: https://leetcode-cn.com/problems/sqrtx/
[double sqrt _doube x_]: https://www.lintcode.com/problem/586/
[https_www.lintcode.com_problem_28]: https://www.lintcode.com/problem/28/
[LintCode]: https://www.lintcode.com/problem/38/
[Link 2]: https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/
[Link 3]: https://leetcode-cn.com/problems/search-a-2d-matrix-ii/