二分查找的递归和非递归

查找算法

常见的查找算法大概有顺序查找、二分查找、二叉排序树查找、哈希表法（散列表）、分块查找等，
下面简单了解一下其他几种查找算法。

1.顺序查找

也就是暴力方法，按顺序比较每个元素，直到找到关键字为止。
条件：无序或有序数据，时间复杂度：O(n)

2.二叉排序树查找

二叉排序树的性质：
1. 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2. 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
3. 它的左、右子树也分别为二叉排序树。

在二叉查找树b中查找x的过程为：
1. 若b是空树，则搜索失败，否则：
2. 若x等于b的根节点的数据域之值，则查找成功；否则：
3. 若x小于b的根节点的数据域之值，则搜索左子树；否则：
4. 查找右子树。

时间复杂度：O(\log_2(n))　　

3.哈希表查找

创建哈希表（散列表）
哈希查找的操作步骤：⑴用给定的哈希函数构造哈希表⑵根据选择的冲突处理方法解决地址冲突⑶在哈希表的基础上执行哈希查找。
建立哈希表操作步骤： ① 取数据元素的关键字key，计算其哈希 函数值。若该地址对应的存储 空间还没有被占用，则将该元素存入；否则执行step2解决冲突。 ② 根据选择的冲突处理方法，计算关键字 key的下一个存储地址。若下一个存储地 址仍被占用，则继续执行step2，直到找 到能用的存储地址为止。 
时间复杂度：几乎是O(1)，取决于产生冲突的多少。

4.分块查找

将n个数据元素"按块有序"划分为m块（m ≤ n）。
每一块中的结点不必有序，但块与块之间必须"按块有序"；
即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字；
而第2块中任一元素又都必须小于第3块中的任一元素，……。
然后使用二分查找及顺序查找。

二分查找

一般是操作有序数组，查找过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；
如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。

这种搜索算法每一次比较都使搜索范围缩小一半。时间复杂度：O(logn)。

二分查找的应用

二分查找一般是用在有序序列的查找，很多时候查找需要结合排序操作来进行。
但是需要注意，二分查找并不一定非要在有序序列中才能得到应用，
只要在二分之后可以淘汰掉一半数据的场景，都可以应用二分搜索。

递归和非递归实现

二分查找和斐波那契查找

折半查找，一般将待比较的key值与第mid=（low+high）/2位置的元素比较，
同时为了防止溢出，使用更高效的移位，也可以记做 mid=low+((low+high)>>1)。
比较结果分三种情况
1）相等,mid位置的元素即为所求
2）> ,low=mid+1;
3）< ,high=mid-1;

斐波那契查找要求元素表中记录的个数为某个斐波那契数减1，即n=Fk-1;
斐波那契数列：0、1、1、2、3、5、8、13、21、……
如果设F(n）为该数列的第n项（n∈N）。那么这句话可以写成如下形式：
F(0) = 0，F(1)=1，F(n)=F(n-1)+F(n-2) (n≥2)，
这是一个线性递推数列，斐波那契数列的算法实现经常在数据结构教材的递归一节中出现。

对于二分查找，分割是从mid=(low+high)/2开始；而对于斐波那契查找，分割是从mid = low + F[k-1] - 1开始的； 通过上面知道了，数组a现在的元素个数为F[k]-1个，即数组长为F[k]-1，mid把数组分成了左右两部分， 左边的长度为：F[k-1] - 1， 那么右边的长度就为（数组长-左边的长度-1）， 即：（F[k]-1） - （F[k-1] - 1） = F[k] - F[k-1] - 1 = F[k-2] - 1。

斐波那契查找的核心是：
1）当key=a[mid]时，查找成功；
2）当key<a[mid]时，新的查找范围是第low个到第mid-1个，此时范围个数为F[k-1] - 1个，即数组左边的长度，所以要在[low, F[k - 1] - 1]范围内查找；
3）当key>a[mid]时，新的查找范围是第mid+1个到第high个，此时范围个数为F[k-2] - 1个，即数组右边的长度，所以要在[F[k - 2] - 1]范围内查找。

与二分查找相比，斐波那契查找它只涉及加法和减法运算，而不用除法（用“>>1”要好点）。因为除法比加减法要慢，在海量数据的查找过程中，这种细微的差别可能会影响最终的效率。