2021/8/23非递归二分查找法填坑，递归形式二分查找法
昨天弄非递归形式的二分查找法的时候，发现如果输入一个数，在被查找数组里没有的时候，如果这个数比数组里的所有数都大，那么会返回数组最大下标+1，如果比所有数都小，返回0，还有一个是如果返回的数在数组范围内的情况
前两个都在昨晚按流程走一遍了，今天走一下昨晚最后那个（处在这个数组的范围内的，数组没有这个数的）
初步看了一下，发现这个GitHub的作者写的程序好像有一点不太严谨
作者这里把情况分为了三种，一个是num[mid]<key，一个是num[mid]>key，另一个就是else了（按目前来看，应该就只有num[mid]==key才可以执行else）
按key=17来走一下流程
mid=0+9/2
=0+4
=4
num[4]=15
15<17
low=4+1=5
mid=5+(9-5)/2
=7
num[7]=25
25>17
high=7-1=6
mid=5+(6-5)/2
=5
num[5]=18
18>key17
high=6-1=5
现在low=high=5了，再走一轮，因为现在mid也是5，所以还是18>17的情况，也就是说high变成4会结束循环
return low;
得到的就是5
这个二分查找法好像有点问题呀....
然后是看看递归形式的二分查找法
说实在的，我还真不知道为啥要叫递归形式的
这个是源码
这个源码里把search方法设了四个参数，数组、low、high跟关键值key
然后把原先非递归形式里的while循环改成了一个递归调用
return再走一遍这个search函数
好像就是把while循环换成了递归....
这样好像比较高级一点？是不是也更省性能呢？日后回来填坑填坑
稍微查了一下递归跟循环，涉及到了好多数据结构的东西，有一点看不懂...
另外还有一个叫迭代的知识点
稍微查了一下CSDN上的资料
https://blog.csdn.net/u013001137/article/details/90116054?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522162972265016780274197182%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=162972265016780274197182&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_ecpm_v1~rank_v29_ecpm-1-90116054.first_rank_v2_pc_rank_v29&utm_term=%E9%80%92%E5%BD%92%E8%B7%9F%E5%BE%AA%E7%8E%AF%E5%8C%BA%E5%88%AB&spm=1018.2226.3001.4187
稍微做一个简单一点的总结
相同点：递归跟循环都是针对需要重复地多次计算相同的问题
不同点：
1.递归是在一个函数的内部调用这个函数本身
2.循环是通过设置计算的初始值及终止条件，在一个范围内重复计算
3.递归相对来说要用的语句比较少
4.在树的前序中序后序遍历算法的代码中，递归的实现方式也比循环简单得多而且更容易实现
面试的时候尽量用递归，如果面试官没有特别要求的话
递归的缺点：