服务器之家

服务器之家 > 正文

一篇文章带你了解C语言二分查找

时间:2021-12-22 14:37     来源/作者:ZDDWLIG

我们常常需要对数据进行查找,修改,查找数据有许多方法,我们先看看最简单的顺序查找

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int main()
{
    int i, k = 0;
    scanf("%d", &k);
    int arr[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    int sz = sizeof(arr) / sizeof(arr[0]);
    for (i = 0; i < sz; i++)
    {
        if (arr[i] == k)
        {
            printf("找到了,它是%d", arr[i]);
        }
    }
    return 0;
}

顺序查找绝大多数情况有效但是由于它是一个一个元素进行查找,其效率很低,只有一个for循环所有其时间复杂度为O(n)。我们希望有一个更高效的查找方法,接下来便是二分查找,先来看看一个顺序查找和二分查找的直观比较。

一篇文章带你了解C语言二分查找

从上面的图中我们感受到二分查找的关键:找到最左边元素(low)和最右边元素(high),确定中间元素(mid),比较中间元素(mid)和目标元素(k)的大小,调整low和high,再确定新的mid....我们要不断确定mid直到找到k,自然需要用到循环,我们有明确的目标:找到k。因此选择while循环,找到k后循环不再进行,而当low和high之间还有元素,即low在high的左边或与之重合,k就依然可能存在,所以循环条件为low<=high,接下来的问题在于怎样调整low和high的值,mid和k比较无非就三种情况:mid<k,mid>k,mid=k。第一种情况,k在mid的右边,我们将low调整为mid+1,high不用调整;第二种情况,k在mid的左边,我们将high调整为mid-1,low不用调整。最后一种情况最简单,我们已经找到了k,直接将mid打印出来就行了,代码如下:

?
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
#include <stdio.h>
int main()
{
    int k = 0;
    scanf("%d", &k);
    int arr[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    int sz = sizeof(arr) / sizeof (arr[0]);
    int low = 0;
    int high = sz-1;
    while (low <= high)
    {
        int mid = (low + high) / 2;
        if (arr[mid] > k)
        {
            high = mid - 1;
        }
        else if (arr[mid] < k)
        {
            low = mid + 1;
        }
        else
        {
            printf("找到了,它是:%d", arr[a]);
            break;
        }
    }
    if (l>r)
        printf("没找到,请重新输入");
    return 0;
}

二分查找的时间复杂度的问题:总共有n个元素,每次查找的区间大小就是n,n/2,n/4,…,n/2^k(接下来操作元素的剩余个数),其中k就是循环的次数。由于n/2^k取整后>=1,即令n/2^k=1,可得k=log2n,(是以2为底,n的对数),所以时间复杂度可以表示O(logn),确实比顺序查找快不少,但是二分查找有一个较大的局限性:只能查找有序数组的元素,即组数字必须是升序或降序。

总结

本篇文章就到这里了,希望能给你带来帮助,也希望您能够多多关注服务器之家的更多内容!

原文链接:https://blog.csdn.net/ZDDWLIG/article/details/119886256

标签:

相关文章

热门资讯

yue是什么意思 网络流行语yue了是什么梗
yue是什么意思 网络流行语yue了是什么梗 2020-10-11
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
2021年耽改剧名单 2021要播出的59部耽改剧列表
2021年耽改剧名单 2021要播出的59部耽改剧列表 2021-03-05
蜘蛛侠3英雄无归3正片免费播放 蜘蛛侠3在线观看免费高清完整
蜘蛛侠3英雄无归3正片免费播放 蜘蛛侠3在线观看免费高清完整 2021-08-24
返回顶部