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

目录

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

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

2. 求开根号 sqrt(x)

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

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

3. 二维矩阵中找target

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

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

4. 拓展应用题

例6. 一维排序数组中找正确的插入位置

例7.  统计比给定整数小的数的个数

例8.  一维排序数组寻找 target 出现的区间

例9.  寻找第一个错误的版本

5. 旋转数组

例10. 寻找旋转排序数组中的最小值（无重复元素）

例11. 寻找旋转排序数组中的最小值（有重复元素）

例12. 寻找旋转排序数组中的指定target（无重复元素）

例13. 寻找旋转排序数组中的指定target（有重复元素）

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

参考：九章算法

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

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

模板如例1所示：

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

理解二分法的三个层次：

• 1. 定义头尾指针，取中点，判断往哪里走；
• 2. 分析问题是什么：是 寻找第一个满足条件的位置，还是最后一个满足条件的位置；
• 3. 保留谁：保留剩余的一定有解的一半。

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

描述：

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

输入：

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

输出：2

模板代码：

找 第一个 = target 的位置

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 &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) { //模板变化部分 (如 last positon: 变化两个if前后顺序)
            return start;
        } 
        if (nums[end] == target) {
            return end;
        }

        return -1;
    }
};

拓展：

• last position: lintcode 458 · 目标最后位置 （最后一个 = target 的位置）
• any position: leecode 

Tips: 递归recursion与while-loop

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

2. 求开根号 sqrt(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 = target) { return end; //比如[1,2,3] target=3 } return A.size(); //比如[1,2,3] target=4 } }; 例7.  统计比给定整数小的数的个数

lintcode 248 https://www.lintcode.com/problem/248/

描述

给定一个整数数组 （下标由 0 到 n-1，其中 n 表示数组的规模，数值范围由 0 到 10000）(可能有重复元素)，以及一个 查询列表。对于每一个查询，将会给你一个整数，请你返回该数组中小于给定整数的元素的数量。在做此题前，最好先完成 线段树的构造 and 线段树查询 II 这两道题目。

样例 1:

输入: array =[1,2,7,8,5] queries =[1,8,5]
输出:[0,4,2]

样例 2:

输入: array =[3,4,5,8] queries =[2,4]
输出:[0,1]

 样例 3:

输入: array =[1,1,1,1,1,1] queries =[1,2,3,4]
输出:[0,6,6,6]

代码

该题 基本上等价于 “例6. 一维排序数组中找正确的插入位置”， 也是寻找 第一个 >= target 的位置，区别在于搜索的数组是无序的，另外可能有重复元素。

class Solution {
public:
    /**
     * @param A: An integer array
     * @param queries: The query list
     * @return: The number of element in the array that are smaller that the given integer
     */
    vector countOfSmallerNumber(vector &A, vector &queries) {
        // write your code here
        sort (A.begin(), A.end());
        vector result;
        for (int i = 0; i < queries.size(); ++i) {
            result.push_back(smallerThanTarget(A, queries[i]));
        }

        return result;
    }

    //排序数组中找第一个>=target的元素位置
    int smallerThanTarget(vector & A, const int target) {
        if (A.empty()) {
            return 0;
        }
        int start = 0;
        int end = A.size() - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (A[mid] == target) {
                end = mid; //注意：考虑可能有重复元素
            } else if (A[mid] < target) {
                start = mid;
            } else {
                end = mid;
            }
        }

        if (A[start] >= target) { //注意: 找第一个>=target的元素位置
            return start;
        }
        if (A[end] >= target) {
            return end;
        }

        return A.size(); // 等价于 ruturn end + 1; //特别注意： 如[1,2,2,3] target = 4
    }
};

例8.  一维排序数组寻找 target 出现的区间

61 · 搜索区间 lintcode

描述

给定一个包含 n 个整数的排序数组，找出给定目标值 target 的起始和结束位置。

如果目标值不在数组中，则返回[-1, -1]

样例 1：

输入：

数组 = []
target = 9

输出：

[-1,-1]

解释：9不在数组中。

样例 2：

输入：

数组 = [5, 7, 7, 8, 8, 10]
target = 8

输出：

[3,4]

解释：数组的[3,4]子区间值为8。

挑战: 时间复杂度 O(log n)

代码

这时 first position = target  和 last position = target 的综合罢了, 其他没什么区别，（也有人尝试将两种方法加flag合并, 个人认为这样只是减少了代码量，逻辑上就不那么清晰了）。

时间复杂度 2O(logN) = O(logN)

class Solution {
public:
    /**
     * @param A: an integer sorted array
     * @param target: an integer to be inserted
     * @return: a list of length 2, [index1, index2]
     */
    vector searchRange(vector &A, int target) {
        // write your code here
        vector internal(2);
        internal[0] = findFirstPosition(A, target);
        internal[1] = findLastPosition(A, target);
        return internal;
    }

    int findFirstPosition(vector & A, int target) {
        if (A.empty()) {
            return -1;
        }
        int start = 0;
        int end = A.size() - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (A[mid] == target) {
                end = mid; //first position
            } else if (A[mid] < target) {
                start = mid;
            } else {
                end = mid;
            }
        }

        if (A[start] == target) { //first position
            return start;
        }
        if (A[end] == target) {
            return end;
        }
        return -1;
    }

    int findLastPosition(vector & A, int target) {
        if (A.empty()) {
            return -1;
        }
        int start = 0;
        int end = A.size() - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (A[mid] == target) {
                start = mid; //last position
            } else if (A[mid] < target) {
                start = mid;
            } else {
                end = mid;
            }
        }

        if (A[end] == target) { //last position
            return end;
        }
        if (A[start] == target) {
            return start;
        }
        return -1;
    }
};

例9.  寻找第一个错误的版本

leecode 278. 第一个错误的版本 = lintcode 74 · 第一个错误的代码版本

描述

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

 示例 1： 

输入：n = 5, bad = 4  输出：4

解释： 调用 isBadVersion(3) -> false  调用 isBadVersion(5) -> true  调用 isBadVersion(4) -> true 所以，4 是第一个错误的版本。

示例 2：

输入：n = 1, bad = 1  输出：1

提示：1