二分查找的递归和非递归

  1. 云栖社区>
  2. 博客>
  3. 正文

二分查找的递归和非递归

范大脚脚 2017-11-15 20:05:00 浏览719
展开阅读全文

一、查找算法

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

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)。

三、二分查找的应用

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

四、递归和非递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
public static int binSearch(int[] arr,int des){
         
        if(arr==null || arr.length<1){
            return -1;
        }
         
        int left=0;
        int right=arr.length-1;//注意防止数组下标越界
        /**
         * 这里的判断条件必须包含等于,
         * 考虑{1,2,3},查找1,如果不判断等于,就丢失了比较导致查找错误
         */
        while(left<=right){
            int mid=left+(right-left)/2;
            if(des==arr[mid]){
                return mid;
            }else if(des<arr[mid]){//舍弃右侧
                /**
                 * 注意,此处的mid已经参与过比较了并失败了,
                 * 所以重新二分不要包含进来,下同
                 */
                right=mid-1;
            }else{//舍弃左侧
                left=mid+1;
            }
        }
        return -1;//查找失败 返回-1
    }
     
    /**
     * @Title: bSearchRecursion
     * 递归参数有不同,left和right明显在每次递归时都是变的
     */
    public static int binSearchRecursion(int[] arr,int left,int right,int des){
         
        if(arr==null || arr.length<1){
            return -1;
        }
         
        if(left<=right){
            int mid=left+(right-left)/2;
            if(des==arr[mid]){
                return mid;
            }else if(des<arr[mid]){//舍弃右侧
                return binSearchRecursion(arr,left,mid-1,des);
            }else{//舍弃左侧
                return binSearchRecursion(arr,mid+1,right,des);
            }
        }
        return -1;
             
    }

  

五、二分查找和斐波那契查找

折半查找,一般将待比较的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”要好点)。因为除法比加减法要慢,在海量数据的查找过程中,这种细微的差别可能会影响最终的效率。

 


本文转自邴越博客园博客,原文链接:http://www.cnblogs.com/binyue/p/5219689.html,如需转载请自行联系原作者

网友评论

登录后评论
0/500
评论