# Introduction

## 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:** 往往没有给你一个数组让你二分同样是找到满足某个条件的最大或者最小值

![](https://3755400284-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M33ghpQv0ZbnP8UX-Qg%2F-M33gjHLI-_g2orPt5LN%2F-M33gnXBi8BqAiG_w3_e%2F%E5%BE%AE%E4%BF%A1%E6%88%AA%E5%9B%BE_20160616162115.png?generation=1584921841738384\&alt=media)![](https://3755400284-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M33ghpQv0ZbnP8UX-Qg%2F-M33gjHLI-_g2orPt5LN%2F-M33gnXD3ovCVT9-s0kL%2F%E5%BE%AE%E4%BF%A1%E6%88%AA%E5%9B%BE_20160616162131.png?generation=1584921842054132\&alt=media)![](https://3755400284-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M33ghpQv0ZbnP8UX-Qg%2F-M33gjHLI-_g2orPt5LN%2F-M33gnXFZNYLFwk-FPvX%2F%E5%BE%AE%E4%BF%A1%E6%88%AA%E5%9B%BE_20170430134051.png?generation=1584921842403178\&alt=media)![](https://3755400284-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M33ghpQv0ZbnP8UX-Qg%2F-M33gjHLI-_g2orPt5LN%2F-M33gnXH6ZFWBiYLWaw0%2F%E5%BE%AE%E4%BF%A1%E6%88%AA%E5%9B%BE_20170430134114.png?generation=1584921842051669\&alt=media)