#学习笔记
第3周-第8课 | 分治、回溯
1. 分治、回溯的实现和特性
- 分治和回溯其实本质上就是递归，只不过它是递归的其中一个细分类。可以认为分治和回溯最后就是一种特殊的递归或者是较为复杂的递归即可。
- 碰到一个题目就找它的重复性，重复性有最新的重复性或者是有苏伟的最优重复性，那么最优重复性就是动态规划。最近的重复性就是根据重复性怎么构造以及怎么分解就有什么分治或者是最后要回溯或者是其他的各种办法。但本质上其实就是一种递归，而本质上的话其实就是找它的重复性。
- 分治的思想是什么
- 它其实就是一种递归，只不过它在递归的状态树的时候，对于一个问题，它要化解成好几个子问题。
- 什么地方不需要化成一个子问题，基本上是没有。如果非要举个例子，可以认为之前求阶乘的题目，每次你要求n的阶乘，就转换成n再乘以n-1，那它的子问题其实就只有一个，子问题虽然没有那么多，但的确它也有子问题。而其他的比如说Fibonacci数列、爬楼梯、抛硬币这种问题，都是分解成多个子问题。
- 为什么很多的问题都需要分治呢？
- 因为一个大的问题之所以为大问题，肯定是有很多细的子问题组成，不然的话它就不算一个大问题或者是不算一个复杂的问题了。所以既然这个问题看似比较复杂或者是相对来说能进入比较高级的面试、要用高级的算法，那它来说是相对复杂的。那相对复杂要怎么用程序解决，其实就是找重复性，找到重复性之后你会发现一个大问题。它肯定是重复，那就能够分成若干的子问题，最后就变成分治这样一种算法。
- 透过这些现象看到问题的本质，就是重复性。所以不管是递归不管是分治或者回溯或者是其他的办法，其实最后本质上就是找重复性以及分解问题和最后组合每个子问题的结果，都是这一个思路。为什么是这个思路？我们用的程序语言都是非常傻的语言，它只支持if else for loop 还有recursion，所以的话最后就变成是它的重复性的一种，不断地反复和迭代。
- 分治应该怎么求
- 一个字符串abcdefghij要把它转成大写的字符串怎么做？正常情况下写一个循环就行了或者调个库函数一下子把所的字符串全部都转过去。
- 分治是什么呢？先拆分成子问题，每个子问题就是相应的每个字符，那么要做的就是对每一个字符都转换成一个大写的，然后最后在拼回去，然后就变成一串大写的字符串。其实它的代码模板的话和递归的代码模板是一模一样的。
- 随堂练习：现场默写范型递归代码模板
- 这里分治的话其实从概念上或者结构上可以说是和递归一模一样的，它最后的话也是需要reverse state，但是在这里多加了一个，就是把这些结果组装成一个大的结果最后返回。如果非要说它和泛型递归有一点不同的话，就是它最后这些资结果要再进行一个组合就这样。那么泛型递归的话，有些时候可以直接递归得到结果，比如之前写的左括号右括号不断排列组合的，就是拼出各种排列组合的结果，就可以直接print。但有些时候必须把每一个子问题它的中间结果全部都组合起来，然后得到最终的结果再返回回去，可能这一点就是一个小的区别。当前在最后的话也需要revert。所以可以认为它是比递归的话多了一步，多的这一步在drill down 和revert state中间再加一步。就是把这些drill down得到的这些子结果要合并在一起返回回去。这样理解递归、分治、回溯其他的都可以把它串在一起，其实他们思想都是一致的。
- 分治代码模板具体写些什么
- recursion terminator就是problem解决了，它其实本质上就是递归的层级，到了最下面的这个层级，也就是到了它的叶子结点，而叶子结点对于分治，一般来说它的叶子结点到达的标志就是在于这个子问题没有了，没有问题需要再解决了。
- 处理当前逻辑，其实就是把这个大问题看如何分成子问题。举个例子求n的阶层，这里的话就是写成n再乘以fac(n - 1)，就是把n单独乘出来，然后去开始调n - 1 的阶乘。如果是fibonacci的话，就是在这里变成两个n - 1 的递归结果，再加上n - 2 的递归结果。如果是组合左右括号的话，那么在这里就是分别组装左括号，存在一个变量里面去，或者是组装右括号存起来，当然要判断左右括号是否用完，类似于这样。
- drill dowm 就是调用这个函数下探到下一层。这里它虽然名字叫divide conquer然后subproblem，其实就是调这个函数下探到下一层，解决更细节的子问题。把这个比喻成公司的组织结构里面，每一个不同层级的人就解决自己层级的问题。其实可以看到一个复杂的问题，本身它的解决方法是异曲同工的，不管是在现实生活中还是在程序里面，最后就组装这个结果，然后返回回来就行了。
- 这里最关键的一点是给一个现实题目或者面试题目，怎样把它拆分成子问题比较重要，主要看经验。而这个的话其实就是所谓的架构师经常完成必须做的事情。还有一点就是说怎样来merge这些subresult，得道这些子结果怎么把它合并起来可能也有个讲究。还有中间的话可能还需要做一些事情，假设比较复杂的这种分治或者比较复杂的公司组织结构，经常要做一件事情，就是中间的结果。比如说子结果一、子结果二、子结果，如何做质量控制和质量保证的，也就是下面的人给你一个返回结果，怎么知道他做的好还是不好，以及在公司的时候根据这些结果的好坏给下面完成这些子任务的人以相应的激励，这就成为了一个比较丰满的公司的组织文化，所以来看其实就是分治的结果。这里还有一点就是和自顶向下的编程思想一致。当前层就只要考虑当前层的问题，一般说不要下探或者至少不要下探太多，一方面人脑不太擅长用人肉递归，当做人肉递归的话，会经常觉得很累而且容易搞错。第二如果要一杆子插下去，干扰别人做事的话，其实在公司组织结构，这是一种微管理或者是事无巨细的话是很讨厌的，程序也是如此。
- 回溯 Backtracking from 百度百科
- 之所以叫回溯的话，就把它理解成一种递归的情况或者是递归的一种问题。
- 回溯采用试错的思想，它尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其他的可能的分步解答再次尝试寻找问题的答案。
- 回溯法通常用最简单的递归方式来实现，在反复重复上述的步骤后可能出现两种情况：
- 找到了一个可能存在的正确答案。
- 在尝试了所有可能的分步方法后宣告该问题没有答案。
- 在最坏的情况下，回溯法会导致一次复杂度为指数时间的计算。
- 这里想表达的一个意思就是不断地在每一层去试就行了，每一层有不同的办法，那么就一个一个一个去试，看这个方法行不行。它最典型的应用的话是在八皇后问题以及数独上面。
- 一个简单的问题的话，就是给你n个括号组，生成有效的括号组合。在中间这里就是把所有可能的解或者所有备选的括号都往里面放，放到最后之前再来看这里放左括号到底是行还是不行。只不过在回溯的时候，要是尽早地可以判定当前的结果是不行的，其实可以越节省执行次数以及执行时间。那么它的代码模板其实就类似于用这样的一个泛型递归的代码模板即可。
- 回溯本身的话，其实它有一种所谓的归去来兮的感觉，这种感觉的话不管在这个题目，整个递归的话其实也就是所谓的归去来兮的感觉。
2. 实战题目解析：Pow(x,n)、子集
3. 实战题目解析：电话号码的字母组合、N皇后
第3周-第9课 | 深度优先搜索和广度优先搜索
1. 深度优先搜索、广度优先抖索的实现和特性
- 关于搜索和遍历它们要做的一件事情，首先搜索来说的话，我们绝大多数情况下处理的都是叫所谓的暴力搜索，或者是说比较简单朴素的搜索，也就是说在搜索的时候没有任何所谓的智能的情况在里面需要考虑。很多情况下它做的一件事情，就是把所有的结点全部遍历一次，然后找到你要结果。
- 那么基于这个数据结构的话，如果这个数据结构本身是没有任何特点的，也就是说是一个很普通的树或者很普通的图，那么我们要做的一件事情就是遍历所有的点，同时保证每个点访问一次，且仅访问一次，最后找到结果。
- 那么把搜索整个先化简情况，就收缩到在树的这种情况下来进行搜索或者是图的情况下。
- 如果在这个树里面要找需要的一个值要怎么做？就是从根这边开始，先搜左子树，然后再往下一个一个点走过去，然后走完之后再走右子树，直到找到需要找的点。这就是采用的方式。
数据结构是怎么定义的？它只有左子树和右子树。- 要实现这样一个遍历或者搜索的话，要保证的事情就是每个节点都要访问一次。
- 且每个结点仅访问一次。且仅访问一次的意思就是代表在搜索中，不想做过多无用的访问，不然访问效率会非常的慢，非常的低。
- 对于节点的访问顺序不同就可以分为深度优先和广度优先搜索这两个。当然还有其余的搜索的话就不再是深度优先或广度优先了，而是按照优先级优先，当然也可以随意定义。比如从中间优先类似于其他东西，但只不过的话定义要有现实中的场景。
- 所以可以认为是一般来说深度优先广度优先，另外就是优先级优先。按照优先级优先搜索的话，其实更加适用于现实中的很多业务场景，而这样的算法一般把它称为启发式搜索。而这个估价函数，以及搜索的整个效率的问题就已经超出了这门课的范畴，而更多的是深度学习的。而这种比如说优先级优先的话，在狠毒偶时候现在已经应用在各种推荐算法和高级的搜索算法，让你搜出你自己最感兴趣的内容，以及你每天打开抖音、打开快手就给你推荐你最感兴趣的内容其实就是这个原因。
- 深度优先搜索怎么来做的
- 深度优先搜索的话整个代码就是各种递归。那么递归这么写的话一开始就是递归的中止条件，然后处理当前的层，然后再下转。那么处理当前层就是相当于访问了结点node，然后把这个结点node加到已经访问的结点里面去，那么中止条件的话就是，如果这个结点之前已经访问过了那就不管了，那么下转的话就走到它的子节点去。它的子节点的一般来说是二叉树的话，就是左孩子和右孩子。如果是图的话，就是它的联通的相邻结点。如果是多叉树的话，就是一个children，然后把所有的children遍历一次。
- 深度优先搜索
- 为了全面性，如果它是一颗多叉树的情况，它的代码和递归的写法上面基本上是一致的，只不过的话在这里就是把判断一个结点是否被访问过放在函数的最开始，而这后面是把新的结点加入到接下来要访问的结点的时候再判断其实是一样的。只不过在这里要保证新加入这个结点是没有访问过的。
- 深度优先搜索或者深度优先遍历，它的整个遍历顺序毫无疑问根节点永远是最先开始的，根节点开始后，往哪个分支走其实都一样的。简单起见就是从最左边开始走，那么它深度优先就会走到底。当1234走完了之后，再接下来走567再走8再走9和10，它的代码其实就是DFS代码 - 递归写法。这块代码要在脑子里面或者画一个图把它的递归起来的话，把递归的状态树画出来会发现就是一个树的结构。就比如说它开始刚进来传的是root的话，root就会先放到visited里面，表示root已经被visit，1的话就表示它已经被visited，被visited之后就从root.childern里面找next_node，所有它的next_node都没有被访问过的，所以它就会先访问最左边这个结点。这里注意当他最左边这个结点先拿出来了，判断没有在visited里面，因为除了root之外，其他结点都没有被visited过，那么没有的话它就直接调dfs，next_node就是把最左边结点放进去，在把visited也一起放进去，递归调用的一个特色就是，它不会等这个循环跑完，它就会直接进到下一层了，也就是当前梦境写了一层循环，但是在第一层循环的时候，我就要开始下转到新的一层梦境里面去了，所以在这里当访问了1之后，在这层循环里面就会访问2，访问2的时候再马上就继续下转，转到3的话，它也会马上继续下转它的孩子就转到4了，然后把这个访问之后在回去，看3有没有其他的儿子，2有没有儿子，然后再回到根节点1，1有另外一个儿子就是5，然后就5、6、7类似的，然后回到5，5还有一个节点就是8，总共就走完了。
- 这个顺序一定要习惯，但是最关键的是把这个代码以及这个代码的整个逻辑以及当它call dfs的话，它会不等这个循环走完，就马上扩到新的一层去。
- 图里面的话其实也类似，假设从S结点开始走的话，它会先走A，当然它走A走B走C都是一样的，就假设它先走A，走了A之后它不会继续走B和C，它就马上会在再走更深一层次的下一个节点D，再继续走G。然后走E和走F都是同样的概率，假设它先走E，在走B再继续走S的话，发现S已经访问过了就不走了，回来回溯。所以回到G之后再走下一个分支去F，再走C，C也访问过了，没有的话就回来，这就是所谓的深度优先遍历。
- DFS代码 - 递归写法这个程序模板一定要记下来，然后写得滚瓜烂熟。这个在这里也可以用递归的形态在最开始就检查node是否被访问过，这样的话整个代码就和递归方式更加相似。这里为了严谨就直接改成，最开始是递归终止条件，然后处理当前层这个结果，然后生成新的下一层要访问的结点，然后再调递归去到下一层，就是进行所谓的下转。在进行下转之前，为了严谨起见也在判断一次next_node也没有被访问过。
- 同时它还支持一种非递归的写法，非递归的写法就是手动维护一个栈，把它加进入就行了，这段代码可以再纸上模拟地运行一下，也可以写在程序里面把它每一个状态一个一个打出来，会发现这其实就是模拟一个递归，用栈来进行表示。
- 广度优先搜索
- 广度优先遍历它就不再是用递归也不再就是用栈了，而是用所谓的队列，它的遍历方式是什么呢？从一个具象的角度来分析这些节点会被怎样访问，既然是的广度优先，假设从1开始，就是一层一层一层地向下扩散。所谓的广度把它想象成一个水滴，滴到1这个位置，然后它的水波纹一层一层一层扩散出去就行了，而不管是地震也好，冲击波也好，其他的水波纹等等，都是按照广度优先遍历向外扩散，这在现实中也经常见。所以很多人会觉得这种扩散方式是更加符合人脑的思考方式，而且在一些求最短路的过程中，比如说从1走到4这个结点，最短可以走多少步。那么用广度优先，第一次到达4这个结点话，就是最优的步数。如果是深度优先的话还不好说，还需要多遍历几次。如果是广度优先的话就是1，然后接下来访问234，然后再访问5678，然后再访问9和10，这样就把广度优先的遍历顺序指出来了。
- 两者进行一下对比，广度优先像这么一个简单的图的话，这是一颗树的结构，它的结点就是0123456，它的枝的话就是白色的线，而蓝色的线只是它相应的顺序，并不是说他们之间会有相应的联系。那么广度优先的话，按照开始的时候0，然后12，然后3456，深度优先先走到底之后，再回来看1另外一个节点往下走，再回来之后，再从它另外一个子树往下走，走到底之后再回来，再往下。这就是两者的一个区别，在对称的二叉树里面进行一个对比。
- 那么BFS就是广度优先搜索，它的代码结构也是老生常谈，就是用一个队列来表示，这个队列的话其实就是一个数组，在Java里面的话可能用得更多的话是一个链表或者是用一个双端队列就是deque来表示即可。Python这块里面就用数组来表示。另外的话也可以用它的一个高性能的connection库里面的有一个deque这么一个数据结构。
- BFS代码一开始队列为空，然后把开始结点加入到队列里面去，然后同时话也要维护这么一个visited这么一个节点。接下来要做的是，只要这个队列不为空的情况下，就把这个结点往里面加就行，然后process这个结点，同时话从这个结点扩散出它的周围结点，一次加到队列里面去，这样产生了一个效果就是，对于这个队列的点，我们一个一个访问，同时因为队列本身是先入先出的，所以它就会按照层的结点的顺序，一个一个从队列里面取就行了。也就是说按照排队来看的话，这里产生了一个队列，排队的队列是queue，然后把最开始的结点放到队列里面去，然后每次从队列里面取了之后，把它的儿子结点再放到队列里面去，它就会按照这个层次一下走一下走。就类似于最开始这个程序，把公司的老总放到queue里面，然后每次只要queue不为空的话，把老总取出来，然后拿到老总相关结点，老总的相关结点就是下面的所有的VP或者是总监，然后再把所有的VP和总监放在这个队列里面去，然后再从队列里面拿，拿的顺序都是那种先入先出的，就接下来按照这个层级，把所有的人就一次捋过了一遍这么一个过程。这个过程如果没见过的话，可能会觉得比较突兀或者想怎么想到的，这个都不用管，不用说它怎么发明创造出来的，它是很多前人就是思考了各种方法发现这种方法是最可取或者是最简洁的，只需要记住就行了。这个深度优先和广度优先其实就是简单的就像for loop和recursion一样，就是各种约定俗成和常用的一些写法，把它记住就行了。
- BFS它本身的话就是用一个queue，再用一个循环来实现。
- 而DFS一般的话，它是用一个递归来实现，当然的话DFS也可以手动写一个栈，这样就变成栈来实现了。
- 关于广度优先搜索和深度优先搜索这两个搜索本身是类似于固化的一种程序，就类似于模板一样，一定要把它记住就好了。它的本质无非就是把所有的结点都访问一遍，按照结点访问的次序的不一样，分为深度优先和广度优先，然后就是写的过程中可以用递归的方式，也可以用所谓的循环的方式来进行。用递归的方式的话程序比较简单，因为程序用系统给你自动去维护了一个栈就是它函数的调用栈。而在用广度优先搜索的话，在这里程序就没法帮你维护这么一个queue这样一个数据结构，所以必须手动维护这么一个queue。当前也可以手写维护一个栈的程序。
- 关于DFS、BFS它们的代码模板要多多联系和把它记住，同时在以后写的时候达到脱口而出的熟练程度。
2. 实战题目解析：二叉树的层次遍历等问题
- https://leetcode-cn.com/problems/binary-tree-level-order-traversal/#/description
- https://leetcode-cn.com/problems/minimum-genetic-mutation/#/description
- https://leetcode-cn.com/problems/generate-parentheses/#/description
- 用广度优先搜索完成括号生成题
- https://leetcode-cn.com/problems/find-largest-value-in-each-tree-row/#/description
第3周-第10课 | 贪心算法
1. 贪心算法的实现、特性及实战题目解析
- 贪心算法 Greedy
- 贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。
- 这里注意最后它结局是希望导致全局最好或者最优，但是它为了达到这样的效果，它采用的办法就是在当下选择最好或者最优的，那么在这样一种决策过程中，经常会有人思考，每次我当下选择最好的，会不会全局就是最优的呢？以及中文中有很多成语就来解释这样的情况，比如说只顾眼前、不考虑未来，或者是说可能极端一点的成语叫鼠目寸光之类的。那么这也就造就了这种方法其实有一定的局限性。大部分人其实也就知道用贪心算法，尤其是最基础的贪心，每次当下情况下找最优不一定能够达到全局最优的情况。但是在某些时候可以，在这个时候的话，我们就可以用所谓的贪心算法，以及在很多情况下，贪心算法在某一步可以用贪心算法，然后再全局的话再加一个搜索递归，或者是动态规划类似于这种。
- 贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。
- 贪心算法和动态规划的不同之处在于它对每个子问题的解决方法都做出选择，不能回退。这里说的是贪心算法的最关键是，它对子问题解决办法就直接在当下做出最粗暴的选择，也就是局部最优的选择，同时是不能回退的。如果能回退的话其实就是回溯以及带最优判断的回溯，就叫做动态规划。动态规划只会保存以前的运算结果，并根据以前的结果，对当前进行选择有回退的功能。最典型的区别在于，当贪心算法只对当前做出最优选择，且不会回退。而动态规划的话，会保存之前的运算结果，这里保存很重要。保存之前的运算结果，并且在适当的时候进行所谓的回退，重新选择。
- 贪心：当下做局部最优判断
- 回溯：能够回退
- 动态规划：最优判断 + 回退
- 贪心算法可以解决一些最优化问题，所以选最优选最近选最好之后，都可以用所谓的贪心法。如：求图中的最小生成树、求哈弗曼编码等。因为这两个本身是相对比较固定的，因为在面试的时候基本上很难出现在题目当中，即使出现也基本上是标准的代码模板，直接套用即可。最重要是，然而对于工程和生活中的问题，贪心法一般不能得到我们所要求的答案。如果每次只选眼前最优的情况下，那么一般来说是达不到最终的最优局面的。
- 一旦一个问题可以通过贪心算法来解决，那么贪心算法一般是解决这问题的最好办法。由于贪心法高效性以及其所求得的答案比较接近最优结果，贪心法也可以用作辅助算法或者直接解决一些要求结果不特别精确的问题。
- 在平时的时候处处都是利己的话，你再全局中不一定能得到最优的结果，这个是比较老生常谈的问题了。
- 实战题目：
- Coin Change 特别版本
- 当硬币可选集合固定：Coins = [20, 10, 5, 1]，求最少可以几个硬币拼出总数。比如total = 36。
- 这个时候就可以用一种贪心法，怎么求呢？
- 首先用20先去匹配，20最多可以匹配多少个的话，那么我们就把20能匹配的个数总数全部都减去，假设总数36，20可以用一个，也就36再除以20，整除除得多少表示20可以用多少个。这里36除以20的话只能用一个。那么得到16，16的话再看10也可以用一个就用了一个，还剩6，6的话还剩有一个5，然后再用一个5，再用一个1。这个的话就可以用所谓的贪心算法，先用最大的去匹配，再用次大的再匹配，然后依次下来。为什么它可以用贪心法呢？就是因为这个硬币的话，20、10、5、1前面的硬币，依次是后面这些硬币的倍数。所以如果需要用两个10或者四个5的话，肯定还不如用一个20，因为后面这些的话都是整除前面最大的硬币的。在这种情况下的话，那么可以从数学上来证明贪心法，每次用最大的即可。因为既然能用20，要是选后面的，肯定后面这些会不优于直接选20的情况。
- 贪心算法的反例
- 那么很多时候的话，在这种特殊的情况下，贪心法是成立的，但是要举出反例的话也很容易。这里用贪心法的一个特点就是有它所谓的特殊性，这里的特殊性指的是这里硬币有整除关系，所以用贪心法。但是在大部分情况下，其实是不能用贪心法的。
- 假设这个硬币不再是20、10、5、1这种有整除性关系的时候，而变成非整除关系的硬币可选集合Conis = [10, 9, 1]。假设拼出18，最优的方案是两个9，两个9加载一起十八可。但是如果用最大的10先去匹配之后剩了8，剩了8，9没办法和8匹配。那么就只剩下八个1了，这样的话肯定不是最优的。所以由此可以看出要用贪心算法的话，
- 第一问题比较特殊
- 第二需要能够证明这个地方用最简单粗暴的贪心算法是能够得到最优解的。
- 这个情况已经证明过，能够得到最优解的原因就是因为它的备选硬币树是存在整除关系的，而既然存在整除关系用最大的能够匹配，肯定要优于这些小的来匹配。
- 何种情况下用到贪心算法？
- 使用贪心算法的情况
- 简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。这种子问题最优解称为最优子结构。
- 贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。
- Homework
- https://leetcode-cn.com/problems/lemonade-change/description/
- https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/description/
- https://leetcode-cn.com/problems/assign-cookies/description/
- https://leetcode-cn.com/problems/walking-robot-simulation/description/
- https://leetcode-cn.com/problems/jump-game/
- https://leetcode-cn.com/problems/jump-game-ii/
- 贪心算法的难就难在怎么证明它是可以用贪心算法的，以及贪心的角度可能不一样。有些时候可以正常去用贪心，有些时候必须把问题稍微转化一下，再进行所谓的贪心求解。或者有些时候必须从前往后贪，这是比较常规的套路。但有些时候可能是从后往前进行贪心，而所谓的贪心的套路以及证明傻贪心是可以得到最优解的过程反而更加重要。
第3周-第11课 | 二分查找
二分查找的实现、特性及实战题目
- 二分查找也算是老生常谈的问题，所以这里最关键是化繁为简。
- 二分查找最关键的三个前提条件，这三个前提条件简单说来，一定要把它形成肌肉式的记忆。
- 索引指的是可以用下标进行访问，那么单调性就毋庸置疑，二分查找指的是在有序的里面进行查找，如果它是无序的话就没法进行二分查找，无序的话怎么办？只能从头到尾遍历。
- 目标函数单调性（单调递增或者递减）
- 正式因为它是有序的，能够通过判断它的某些特征排除掉，比如说前半部分或者排除掉后半部分，所以它必须是要单调的，可以是单调递增也可以是单调递减。
- 存在上下接（bounded）
- 如果没有上下界的话，那么它的空间可能是无穷大的，那么它就没法往中间扩。当然有一种特殊的形态，但是出现的情况少之又少。
- 能够通过索引访问（index accessible）
- 很多时候如果是单链表的话，相对来说既是是有序的话，单链表进行二分查找都不是那么容易的，当然如果把单链表进行一些改造，比如说用它所谓的跳表的方式，那就另外别说了。
- 代码模板 要形成肌肉式记忆
- 首先左右边界，分别是0和数组长度减1，也就是左右的下标值，while里面是left小于等于right，所以这条件的话有些时候会变成没有等于号，但是大部分情况下可以认为是有小于等于的，然后得到它的中间值，就是mid这个值。判断mid是否等于target，然后来break或者是return这个result，可以先把等于等于放在这里，只要它等于的话就马上return即可。在这里，这个数组假设是上升的就是升序排列的，如果target大于array [mid]的话说明它在右侧，那么要继续向右查找，所以left就把左界向右进行移动，变成mid + 1了，否则的话说明在左侧，那么右界的话就要向左移动，变成mid - 1这么一个形式。那么根据这里的话是一种所谓的左下界和右下界为整型的情况下，就是为inteeger的情况下，在有些时候可能为实属的情况下，那么就没有所谓的加一和减一，在这就直接等于mid即可。
- 二分查找的形式是什么样子的
- 在递增数组里[10，14，19，26，27，31，33，35，42，44] 查找：31
- 它中间有些数是不连续的，总体的话是单调递增的。
- 如果是正常遍历的话，就需要六次查找，最后查找到等于31。那么用二分的话，算出它的中间值，中间值刚好等于27，31和27进行对比大于27，说明可以排除前半部分，继续从后半部分进行查找，前半部分就不考虑了。后半部分的中间值继续算，mid就等于35，31比35小就说明继续在27的右侧和35的左侧开始查找，又算出来它的mid值等于33，它小于33再继续往这边找，最后就找到了31这个数。
- 所以它是由左右两个边界不断地向中间进行夹逼的过程，这种夹逼的过程又由于这个数组本身他是单调递增的，所以每次可以排除一半，可以认为有点像二叉搜索树一样的特性，但是这里的话它是用所谓的数组来进行实现的，而二分查找本身这种有序性的话，很多时候在数学里面用得特别多，所以对这个逻辑是比较熟练的。
- 所以关键的关键在于把这个代码要写熟。面试时候最大的问题就是写二分经常容易一下子懵了，不知道如何起笔，因为概念都知道，但是要起笔的话就很难，或者是代码里面多多少少都有一些bug，所以在这个时候一定要把这个代码模板写的非常熟练。就一开始就把代码模板全部都打完了，打完了之后再把这些值全部都填好，根据最主要的数组是什么，以及它的左右界到底是小于等于的，还是在这里要加一减一的，还是不用，再进行微调，最后反复地验证是没有问题的。
- 实战题目
- https://leetcode-cn.com/problems/sqrtx/
- https://leetcode-cn.com/problems/valid-perfect-square/