00:00
那接着呢，咱们来看一下这个线性查找之外的这个比较常用的叫二分法查找。诶，二分法查找啊，这个二分法查找呢，它相较于线性查找来讲呢，比较快，哎，比较快啊，这是它的一个特点，嗯，我们呢，可以先稍微的形象点呢，举一个例子，比如说呢，这是一个供电站，这呢是一个村庄，哎，然后呢，马上该过这个农历新年了，哎，这个假设呢，今天就是除夕啊，这个这个村庄呢，每家每户都有店啊，等着看这个春晚呢，是吧？嗯，突然呢，没电了。啊，那没电了，马上就八点了，然后大家都很着急，那这时候呢，你得看一下这个中间这个线路哪块出问题了。啊，那这时候就有两种策略，第一种就是啊，按照这个顺序，一个电线杆一个电线杆的去测，看哪块出问题了，哎，你要测出来了，诶那块就修，修完以后呢，你看有没有电，如果还没电，还得一个一个这样去去看是吧？哎，这是我们说的这种情况啊，这个就是我们所谓的叫线性查找，一个一个去找，那如果这呢有500个电线杆，一个电线杆呢，假设需要一分钟，就是500分钟，500分钟呢，除以60分钟，那大概呢，就得是八个小时，八个小时就就麻烦了是吧，如果点比较正的话呢，第一个就是那你可能一分钟就搞定，那如果要是最后一个是呢，那估计呢就该被开除了，是吧，就太慢了啊，那我们就得考虑怎么能更快一些。
01:35
哎，那这时候呢，我们就考虑，诶每次呢折半，哎，所以二分法查找呢，也叫做折半查找，哎，我呢就上来就定位到中间。啊，你要500个电线杆，我上来就二百五了。不是我二百五找到中间这个电线杆，诶你这块呢，先测一下这个电站跟这块中间通不通。如果这块要通，那行，那这块呢，肯定是这块出问题了，那接下来呢，你就再定位到中间，那静脉中间再去从头这块去测啊，你测这块行不行，这块还行，那就这块有问题，然后再折板，其实折不过几次，是不是就大大的缩减了啊，你想我每次相当于除以二，每次相当于除以二，你反过来就相当于每次乘以二，每次要乘以二，其实大家也知道这是不是就是指数啊，指数呢，你是不是就知道指数增长速度是很快的呀，指数增长到后边呢，猛涨，那现在咱们是倒着来，那就相当于是不是猛跌呀，所以这个这个查找的这个数量一下子大大的就缩减了，所以最后呢，你找到这个问题的时间其实有大大的缩减了，可能几分钟啊，十几分钟可能就搞定了。
02:42
哎，那这时候呢，这个就可以看春晚了是吧？哎，这就我们所说的这个叫二二分法查找，哎，就这个情况啊，哎，刚才呢，我们举的是一个实际问题啊，那在我们这儿的话呢，咱们得看看在这个数组当中，咱们呢，怎么去找啊，这个数组我说呀，其实还不太适合用二分法查找。
03:08
不是少不是少什么问题啊，对，刚才有同学提到说叫有序的。嗯，咱们刚才举的那是一个实际问题啊，它还好在在这呢，其实是有一个变化的哈，你比如说我上来就去中间找，我找比如说我找这个BB，假设我要找的这个数不是BB，那你说你是找左边还是找右边啊对这就不知道了，是吧？所以在咱们这个代码中这块呢，就要求你这个要想能用二分法，前提是他得先有序。所以这呢，我们就写一个前提啊。前提就是嗯，所要查找的这个数组必须有序。在有序的前提下呢，我们再去做查找啊，是这样的啊，那行了，那咱们就不能用上边这个了，我再重新举一个例子吧。
04:07
AR2。诶，我这儿呢，就诶随便的，我写一些这个随机的一些数了。好，写完了啊，然后呢，我们从这些数里边，我去找某一个数，首先呢，我这是一个有序的，至于说你是升序降序，这无所谓，我现在呢，有一个int型的，嗯，我这还能叫DT吗？上面叫过了，叫过了不管跟类型没关系了，只要叫过了就不行，我就叫这个吧，我找这个负34。行，那这是我们要找的话呢，我们也是叫折半或者叫二分法啊，诶我这儿呢，有一个图示，简单看一下，这呢是另外的一个数组了，嗯，如果呢，我们要找的数先跟这个中间的15去比，如果你要是发现比15要是大。
05:14
那接着是不是就从这里边儿找，从这里边呢，再找中间这个发现比这里边儿的这个中间的值小，那就从这里边找，然后这俩呢，你再去看满不满足，如果呢，这俩里边恰好有一个满足，那就找上了，如果要是不满足呢。不满足或者比他大，你就再看这个，这就一个了，这一个你看是不是不是就拉倒，哎就成这种了啊行，咱们怎么来刻画这个问题呢？哎这里边呢，我们提到了中间值的问题，中间值要想得到，你是不是得拿头的这个，跟尾的这个加起来除以二啊，所以我们得先有个初始的啊，比如我叫一个head初始呢，这是零表示的是首索引。
06:00
哎，初始这个索引，哎，初始的手索引。然后呢，我再定一个摁，诶它呢，当最后一个索引索引，所以有个减一。初始的末索引或者叫尾索引行。那我们下边的话，你找一次没找着找两次，两次不行，三次肯定也是个循环了，那循环的话呢，我们这个终止的条件呢，是不是得让你这个head呢，它得不能超过这个N的呀，啊等的时候呢，也得看一下。万一等的时候，中间你等的那个值恰好就是我要找的那个值呢，哎，所以这有个等号啊，嗯，那么进来以后，进来以后的话呢，我们首先要做的就是获取它俩的这个中间的那个值，所以就int型的，我用一个叫middle中间值啊哎，我们用had呢，加上我们的N去除以二对得到中间值，那有可能除不尽，除不尽呢，就拿左边这个对，比如二点几，呃，或者五点几，那就拿五是吧，哎，我取左边这个截断以后的数值就可以啊，那么找到这个咪以后，我们就拿咱们的这个要找到这个值和这个咪，所以位置上这个数呢去比较，如果你恰好发现我们的DIE1就是你要找的这个middle。
07:27
那这时候呢，运气太好了，相当于就找到了我们这呢，就输出一下。啊，跟上边这个一样啊，找到了指定的元素，所以位置为。所位置为米。哎，这样这是比较幸运的啊，找到以后呢，我们也就给他break了啊，这个是比较好的情况啊，那如果呢，你是发现你的A2这个middle它呢大于咱们的DST。
08:04
脑子里边浮现这个结构啊，这是你整个这个结构，然后找到这个中间值，这个中间值咱们先假设这个我是从小到大排列的啊，从小到大排列的情况下，我找到中间值以后，这个中间值比我要找的这个值大。比如这是十，我要找的是五，是不是从左边接着找啊，从左边接着找，那我这要做个什么操作呢。诶对，原来这是头head，这是end，我现在是不是让这end等于middle前一个缩引啊，诶对，所以我就把这个end呢改一下啊，改成我们的middle减一。就可以了，然后接着呢，它再循环回去满足这个情况下呢，再重新计算一个新的密，嗯，然后再else。嗯，再else的话呢，呃，我们就相当于是你这个M的值呢，比较小了。
09:03
这样子，嗯，这样的话呢，我是不是得从后半段找啊，后半段呢，我就相当于是让had等于对middle加乙。哎，其实这个题主体呢，基本上就写完了，就。啊，就是过程呢，其实说清楚以后呢，就是这样写，写完以后接着再去判断判断满足，再来走走走走走，那如果说要是这个没有执行过这个结构，然后break了，或者说整个这个程序，嗯，没有执行到这个结构，那就是没有break，整个呢是通过这个条件给他终止的，就是一旦呢，他要是。哎，走到这儿的话呢，是因为你这个条件不满足的，那就属于没找到啊，跟咱们上边类似，是不是还得去定一个布尔型的变量。Is flag，我写个一啊，写个true，哎，当你要是进去的这种情况呢，哎，我就要is flag给它改成个false，嗯，就是你要是走到这个位置，我们判断一下你到底是因为走进if服结束的，还是说呢，是因为我这个外循环不满足结束的。
10:08
哎，If如果叫is flag1，哎，你要是还是一个处，那就说明没有进去过这个if，哎，那说明就是没有找到啊，那就是哎这个。对吧。哎，是不是这个题目呢，就这样来写来跑一下。哎，找到了这个是，所以是一，哎所以是一，这不就是这个负34嘛，哎，咱们再换一个。嗯，改成一个34啊，34啊，34也有。哎，这是三，哎0123找到了啊，改35。哎，这有没有找到。诶，这呢是一个二分法啊，就是当我们这个数据量比较小的时候呢，其实你好像体验不出来说呃效果多好啊，当然一旦这个数据量很大的时候呢，二分法的效率呢，确实要高一些。
11:09
哎，这个前提要注意啊，如果你要这个速度都没有序了，那那就用不了，所以说呢，这也是一个，呃，辩证法一样啊，就是你想这个快一点，它的条件要求就高一些，找女朋友也这样是吧，就是你想找一个特别好的，那就去，他可能也要求你得好一点是吧，那你现在就得是不断的丰富自己，你才能够找到一个更好的啊啊如果呢，你要找一个像那个如花那样的，他说只要是个男的都行，那你就看你愿不愿意了，就是吧，嗯，行，这是咱们说这个叫二分法查找哈，那有没有同学说，诶还有比二分法更好的吗？或者说为什么能不能三分法，三分法四分法，就是说你为什么找的时候要找中间呢？我我找这个1/3的点行不行。
12:01
啊，我找这个3/4的这个点行不行啊，判断你能判断呀，有没有想过说为什么要找中间的呀，其实其实你找1/3的这个点，呃，或者3/4的点其实都行，其实从这个这个统计上来讲，从均值上来讲，其实是一样的，就均值是一样的啊找中间的话呢，只不过就相当于左边一半，右边右边它是一样的平衡呗，你要是我找这个1/3的点有可能更好，比如说呢，假设你要找那个数恰好在左边这块，你上来就是找这个1点/3或者1点/4，那你是不是离这个要找的数更近呢？对，这就算你运气好了，那要万一在这儿呢，那你就离得不就更远了吗？所以其实从这个均值上来讲，其实跟1/2的是一样的啊，是一样的，那我要是真要用1/3，你还想为什么不1/2呢？那总得有一个，总得选一个吧，是吧，那就1/2了啊，但是呢，确实也也可以有一些更好一点的，哎，让大家就开阔开阔思路哈，你比如说你看我这样说啊，假设我们这个数呢，相对来讲比较均匀一些啊，什么叫均匀一些，就比如说这些数中间的间隔呢，差不太多啊，比如说这是零，假设都是正数啊，这是零，这是五啊，这是一个七啊，这是一个11啊，17就是它相对来讲均匀一些，你别这块突然蹦出来个200多啊。
13:32
那就稍微均匀一些，如果这些数稍微比较均匀的话呢，还是从小到大排列的，或者从大到小都行，只要有序就可以啊，其实还可以改进一下。啊，可以改进一下，就是可以不用这个从中间找啊，什么意思呢？你比如说我们这个数呢，很多啊，相对比较均匀，假设呢，最大这个是100，最小是零，我现在要找的这个数呢，是是十。我要找的是十的话呢，你看我要是用二分法，相当于一开始定位是不是大概50左右啊，然后呢，你这会再再就定位到二十二十五这块了，然后再往前这个再再折板，那能不能更快一点呢？因为你要找这个舒适十，其实大概也知道是不是应该是有点偏向于前特别靠前那个位置了，它其实可以怎么着呢，你要找的这个数呢，减去你这个第一个元素，再除以呢，你最大的这个数减去第一个元素。
14:28
就相当于大概占几分之几的位置，你看我要十减零就是十，然后呢，这个呢，100减零就是100，相当于大概找那个1点/10那个附近，你这个十可能出现的概率会很高，对吧？哎，这就算一种改进哈，哎像这种方式，这个叫哎差值法，后边还有类似的什么这个呃，哈希查找啊，什么费纳些查找啊等等查找这块呢，还有很多的操作，这个大家就不用去，咱们先不用深究了，除非呢你专门去看这个算法了哈，这呢咱们讲这两种就可以了，呃，这两种呢，关于二分法查找呢，大家其实呢啊，就是大家如果上面东西已经很多了，这块呢，先作为一个熟悉就可以了，嗯，就是咱们真正开发的时候呢，用不着你自己去写，都有现成的结构来调的啊。
我来说两句