Binary Search 二分法 笔记

1.Binaery Search on Index - OOXX

找到满足某个添加的第一个位置或者最后一个位置

找满足条件的数组中第一个/最后一个位置

2.Binary Search on Index - Half half

并无法找到一个条件，形成OOXX

可以判断，保留有解的一半，或者去掉无解的一半

3.Binary Search on Result

Given an sorted integer array - nums, and an integer - target

Find the any/first/last position of target in nums

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

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

T(n) = O(1) + T(n/4) + O(1) = O(1) + T(n/8) + O(1) + O(1) = logn + T(1)

T(n) = O(n) + T(n/2) = O(n) + O(n/2) + T(n/4) = O(n) + T(n/8) + O(n/2) + O(n/4)

    = O\(2n\) = O\(n\)

Time Complexity in Coding Interview

• O(1) 极少

• O(logn)几乎都是二分法

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

• O(n) 高频

• O(nlogn) 一般都可能要排序 （数据结构，支持logn操作，循环一遍)

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

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

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

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

Recursion (递归) or While Loop

用 While Loop 不用 Recursion, 除非考得是Recursion 或者复杂问题

Recursion 用到stack 空间， 不推荐， stack v.s. memory,

二分法常见问题

1.死循环

2.循环结束 start < end?

3 指针变化 start = mid?

循环结束条件

start + 1 < end

mid = start + (end - start)/2