vlambda博客
学习文章列表

https://github.com/WiseWolfs/DataStructureAndAlgos

这个GitHub的链接是一些面试常用的数据结构（链表、队列、栈、二叉树、哈希表等）以及一些常用的算法（排序：归并、快速排序、基数排序等，查找：二分查找法），用Java实现的

百度云盘链接：https://pan.baidu.com/s/1s967vfgEBd1vSrfwVI9Y3g 提取码：【be9k】

找资源找到的一本书，算法图解，薅了薅了

晚上学一下二分查找法

通俗易懂地来了解一下二分查找法

首先呢，有一个猜数字的游戏，1-100里有一个数，每次我说一个数的时候它就会说这个数离目标小了还是大了，

假如从1-100，你是从头猜到尾的，肯定是一个很笨的方法

如果像图里这样直接猜中间数，就可以不断缩小范围

这样就是一个很聪明的算法了，使用二分法，每次都能排除一半的数据

100个数字，最多7次就可以准确猜到

不过，二分法只有当列表有序的时候才有用，列表得从小到大或者从大到小

思考：

诶？刚才下午刚好学了排序，说不定这排序跟查找有点渊源？

初级一点的Java工程师不就是增删改查的调用各种来回吗，这增删改查里的查....难道就跟这个算法有关...？

首先先来试试非递归形式的

说实在的...此时此刻在写文的我，并不知道递归是什么意思.....

这个是在GitHub上找来的项目源码

剖析一下

首先是这个BinarySearch类里有个缺省访问权限的int类型的search方法，它有两个参数，一个是int类型的数组叫num，另一个是int类型的方法关键词 key

定义一下各成员变量，

low是二分法的那个区间的头，实际含义是这个数组的某个坐标，从这个坐标开始是二分法的那个区间的头

high是这个区间的尾

mid是中间数组下标

用文字走流程环节：

假设这个num[]是{0，1，2，3，4，5，6，7，8，9}

high=10-1=9

我的key输入为8

那么这个流程为

mid=0+(10-1)/2=4(int类型，向下取整的)

num[4]是4,key是8

4<8,

走if(num[mid]<=high)

low变成mid4+1=5，

重新走回while，low<=high继续成立

mid  = 5+（9-5）/2=7

num[7]=7，key是8

7<8，继续走if(num[mid]<key)的流程

low变成（mid）7+1=8

重新走回while，low<=high继续成立

mid = 8+(9-8)/2

       =8+0

       =8

num[8]=8，key=8

走不了if(num[mid]<key)，也走不了else if(num[mid]>key)

走else，return mid;

此时的mid是8

因为已经走到retrun了，这整个search方法就结束了，停止运行了

可以得到结果是8，此时num[mid]==key，也就是说此时数组里的第9个元素就是key

我们来运行一下程序

没出问题

此时我发现，在这个方法体中，while判断外，方法体内有一个return low;

什么时候会执行这个代码呢？应当是当while(low<=high)不成立的时候

这个GitHub的作者把low定义为了0，higt定义为num.length-1，

这个时候的low<=high不成立，那么这个数组的长度应当是0了

因为要知道哪怕这个数组假设

int num={1};

num.length-1=0;

low<=high也是成立的，可以走下去

所以这个return的作用一来是为了当这个数组为时，直接return low结束代码；

但是我又不禁思考一个问题，假如说这个数在num里根本都不存在，这个GitHub上的项目又会怎样呢？

我先试了试将key输入成99

但我们的mid代表的是数组坐标，10个数从0开始到9就结束了代表10个数，为什么会有10坐标呢？

我从头分析到尾，拿我们的int nums[] = {0,1,8,9,15,18,19,25,29,30}来分析

首先是15的位置成为mid

然后变成了19的位置成为mid

又变成25的位置成为mid

然后是29的位置

到现在只剩下29，30了也就是数组下标8、数组下标9

这时候谨慎一点计算mid

mid=8+(9-8)/2

      =8+0.5 因为是int最后mid=8

（有趣的是，25，29，30的时候29当了一次数组坐标中心

29，30的时候又来一次，有两次mid=8）

因为我输入的key是99，这回仍然是走num[mid]<key

low再一次进行了+1，从8变成了9

low=mid+1

      =8+1

      9

这时候就low跟high一模一样，只剩了30一个数

mid=9+(9-9)/2

      =9+0

      =9

哪怕是mid[9]的30仍然<key=99

那么low又一次赋值为mid+1，

low=mid+1

      =9+1

      =10

然后就不符合while(low<=high)了，走的return low，变成了10

此时 我又发现，这个99虽然不在列表里面，但是它是比这里面都大

如果我输入的数字是比这里面的都小呢？

观察代码，low是不断用mid+1，而输入的key比num里的所有数都小，然后会有high小到跟low相等的时候（low初值为0又因为key比所有num的数都小），这时候再来一次high=mid-1变成了-1

此时不满足while(low<=high)，由于return的是low，那么应该最后的输出是0

我们来输入一下验证看看对不对

确实如此，是0

那么假如说这个{0,1,8,9,15,18,19,25,29,30}

我输入的是一个17呢？它不存在，但是却不是比里面所有的数都大或都小，这时候是什么样呢？

光看第一眼我还真没法确定，我输入一下试试

它最后输出的结果为5！可是下标5根本不等于17

应该是代码有问题，明天尝试解决一下

也许从GitHub上找来的这个项目并不是最完美的二分法

抑或是说，非递归的二分法这个数据结构本身就存在缺陷？弥补这个缺陷还不如直接用递归的二分法？

明天再来解决一下，快过点了，先把今天的学习日记发出去哈哈哈