Introduction

https://labuladong.github.io/algo/2/21/59/

1.Time Complexity in Coding interview

• O(1) 极少

• O(logn) 几乎都是二分法，比O(n)更优的时间复杂度几乎只能是O(logn)的二分法

• O(√n) 几乎是分解质因数

• O(n) 高频

• O(nlogn) 一般都可能要排序

• O(n2) 数组，枚举，动态规划

• O(n3) 数组，枚举，动态规划

• O(2n) 与组合有关的搜索

• O(n!) 与排列有关的搜索

2.面试中是否使用 Recursion 的几个判断条件

1. 面试官是否要求了不使用 Recursion （如果你不确定，就向面试官询问）

2. 不用 Recursion 是否会造成实现变得很复杂

3. Recursion 的深度是否会很深

4. 题目的考点是 Recursion vs Non-Recursion 还是就是考你是否会Recursion？

• 记住：不要自己下判断，要跟面试官讨论！

3.经典二分搜索模板

start + 1 < end （不会陷入死循环）

start + (end - start) / 2

A[mid] ==, <, >

A[start] A[end] ? target

public int findPosition(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }

        int start = 0, end = nums.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                start = mid;
            } else {
                end = mid;
            }
        }

        if (nums[start] == target) {
            return start;
        }
        if (nums[end] == target) {
            return end;
        }
        return -1;
    }

4.二分法本质

T(n) = T(n/2) + O(1) = O(logn)

通过O(1)的时间，把规模为n的问题变为n/2

思考：通过O(n)的时间，把规模为n的问题变为n/2？

T(n)=T(n)+O(n)=T(n/2)+O(n)+O(n/2)=T(n/4)+O(n)+O(n/2)+O(n/4)=...=O(n+n/2+n/4+.....+1)=O(2n)=O(n)

理解二分法的三个层次：

1> 头尾指针，取中点，判断往哪儿走

2> 寻找满足某个条件的第一个或是最后一个位置

3> 保留剩下来一定有解的那一半

5.二分位置：Binary Search on Index:一般会给你一个数组,让你找数组中第一个/最后一个满足某个条件的位置

6.二分答案：Binary Search on Result: 往往没有给你一个数组让你二分同样是找到满足某个条件的最大或者最小值

4.二分搜索问题的泛化

什么问题可以运用二分搜索算法技巧？

首先，你要从题目中抽象出一个自变量 x，一个关于 x 的函数 f(x)，以及一个目标值 target。

同时，x, f(x), target 还要满足以下条件：

1、f(x) 必须是在 x 上的单调函数（单调增单调减都可以）。

2、题目是让你计算满足约束条件 f(x) == target 时的 x 的值。

上述规则听起来有点抽象，来举个具体的例子：

给你一个升序排列的有序数组 nums 以及一个目标元素 target，请你计算 target 在数组中的索引位置，如果有多个目标元素，返回最小的索引。

这就是「搜索左侧边界」这个基本题型，解法代码之前都写了，但这里面 x, f(x), target 分别是什么呢？

我们可以把数组中元素的索引认为是自变量 x，函数关系 f(x) 就可以这样设定：

// 函数 f(x) 是关于自变量 x 的单调递增函数
// 入参 nums 是不会改变的，所以可以忽略，不算自变量
int f(int x, int[] nums) {
    return nums[x];
}

其实这个函数 f 就是在访问数组 nums，因为题目给我们的数组 nums 是升序排列的，所以函数 f(x) 就是在 x 上单调递增的函数。

最后，题目让我们求什么来着？是不是让我们计算元素 target 的最左侧索引？

是不是就相当于在问我们「满足 f(x) == target 的 x 的最小值是多少」？

画个图，如下：

如果遇到一个算法问题，能够把它抽象成这幅图，就可以对它运用二分搜索算法。

算法代码如下：

// 函数 f 是关于自变量 x 的单调递增函数
int f(int x, int[] nums) {
    return nums[x];
}

int left_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0, right = nums.length;
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (f(mid, nums) == target) {
            // 当找到 target 时，收缩右侧边界
            right = mid;
        } else if (f(mid, nums) < target) {
            left = mid + 1;
        } else if (f(mid, nums) > target) {
            right = mid;
        }
    }
    return left;
}

这段代码把之前的代码微调了一下，把直接访问 nums[mid] 套了一层函数 f，其实就是多此一举，但是，这样能抽象出二分搜索思想在具体算法问题中的框架。

运用二分搜索的套路框架

想要运用二分搜索解决具体的算法问题，可以从以下代码框架着手思考：

// 函数 f 是关于自变量 x 的单调函数
int f(int x) {
    // ...
}

// 主函数，在 f(x) == target 的约束下求 x 的最值
int solution(int[] nums, int target) {
    if (nums.length == 0) return -1;
    // 问自己：自变量 x 的最小值是多少？
    int left = ...;
    // 问自己：自变量 x 的最大值是多少？
    int right = ... + 1;
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (f(mid) == target) {
            // 问自己：题目是求左边界还是右边界？
            // ...
        } else if (f(mid) < target) {
            // 问自己：怎么让 f(x) 大一点？
            // ...
        } else if (f(mid) > target) {
            // 问自己：怎么让 f(x) 小一点？
            // ...
        }
    }
    return left;
}

具体来说，想要用二分搜索算法解决问题，分为以下几步：

1、确定 x, f(x), target 分别是什么，并写出函数 f 的代码。

2、找到 x 的取值范围作为二分搜索的搜索区间，初始化 left 和 right 变量。

3、根据题目的要求，确定应该使用搜索左侧还是搜索右侧的二分搜索算法，写出解法代码。

经常有读者问我，读了之前的爆文 二分查找框架详解 之后，二分查找的算法他写的很溜了，但仅仅局限于在数组中搜索元素，不知道底怎么在算法题里面运用二分查找技巧来优化效率。

那我先说结论，你想用二分查找技巧优化算法，首先要把 for 循环形式的暴力算法写出来，如果算法中存在如下形式的 for 循环：

// func(i) 是 i 的单调函数（递增递减都可以）
int func(int i);

// 形如这种 for 循环可以用二分查找技巧优化效率
for (int i = 0; i < n; i++) {
    if (func(i) == target)
        return i;
}

如果 func(i) 函数是在 i 上单调的函数，一定可以使用二分查找技巧优化 for 循环。

「在 i 上单调的函数」是指 func(i) 的返回值随着 i 的增加而增加，或者随着 i 的增加而减小。

为什么满足这个条件就可以使用二分查找？因为这个逻辑和「在有序数组中查找一个元素」是完全一样的呀！

在有序数组 nums 中查找某一个数 target，是不是最简单二分查找形式？我们看下普通的 for 循环遍历算法：

// nums 是一个有序数组
int[] nums;
// target 是要搜索的元素
int target;

// 搜索 target 在 nums 中的索引
for (int i = 0; i < nums.length; i++) {
    if (nums[i] == target)
        return i;
}

既然 nums 是有序数组，你把 nums[i] 看做函数调用，是不是可以理解为 nums 在参数 i 上是单调的？这是不是和之前说的 func(i) 函数完全一样？