Warning: Undefined array key "HTTP_ACCEPT_LANGUAGE" in /www/wwwroot/blog/wp-content/plugins/UEditor-KityFormula-for-wordpress/main.php on line 13
【数据结构】二分查找的实现 – Machine World

【背景】

二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。

【源码运行环境】

操作系统:Windows 10

编译环境:Dev C++(基于C99标准)

【动态图解】

461877-20160721092729169-843824718.gif

461877-20160721092805029-903699213.gif

【源码】

递归实现:

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
/*
*方法名:binary_Search
*作用:折半查找,查找数组中是否存在指定元素,并返回位置
*参数:待查找数组 array; 起始位置 start ; 结束位置 end; 元素 element
*返回值:位置 position
*Author: WellLee
*最后一次修改时间:2018年12月6日 22:18:55 
*/
int binary_Search(int array[], int start, int end, int element)
{
    int mid;
    if(start > end)
    {
        return -999;
    }
    mid = (start + end) / 2;
     
    if(element == array[mid])
    {
        return mid;
    }
    else if(element >= array[mid])
    {
        return binary_Search(array,mid+1, end, element);
    }
    {
        return binary_Search(array,start, mid - 1, element);
    }
}

非递归实现:

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
/*
*方法名:Binary_Search
*作用:折半查找,查找数组中是否存在指定元素,并返回位置
*参数:待查找数组 array; 数组长度 length; 元素 element
*返回值:位置 position
*Author: WellLee
*最后一次修改时间:2018年12月6日 22:27:32
*/
int Binary_Search(int array[],int length, int element)
{
    int start = 0;
    int end   = length;
    int mid = 0;
    while(start <= end)
    {
        mid = (start + end) / 2;
        if(element == array[mid])
        {
            return mid;
        }else if(element > array[mid]){
            start = mid + 1;
        }else{
            end = mid - 1;
        }
    }
    return -999;
     
}

【分析】

折半查找的平均查找长度(ASL)计算公式如下:

假设表中每个记录的查找概率相等为:Pi=1n

ASL=i=1nPiCi=1ni=1hj2j1=n+1nlog2(n+1)1

当n较大时,可近似看做:ASL=log2(n+1)1

因此,折半查找的时间复杂度为O(log2n)

【总结】

折半查找的优点是:比较次数少,查找效率高。

其缺点是:对表结构要求高,只能用于顺序存储的有序表。而有序表的构造需要付出较大的时间代价。

因此,折半查找不适用于数据元素经常变动的线性表。

【参考文献】

  • 《大话数据结构》.程杰.清华大学出版社

  • 《数据结构习题解析与实验指导》.李冬梅,张琪.人民邮电出版社

作者 WellLee

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注