运维开发网
广告位招商联系QQ:123077622
 
广告位招商联系QQ:123077622

C语言算法--有序查找(折半查找/二分查找)

运维开发网 https://www.qedev.com 2021-08-25 10:25 出处:网络 作者: Aaronskr
目录题目解法一: 挨个遍历方法二:折半查找/二分查找(仅适用于有序查找)总结题目
目录
  • 题目
    • 解法一: 挨个遍历
    • 方法二:折半查找/二分查找(仅适用于有序查找)
  • 总结

    题目

    首先我们来把题目瞅一眼:

    在一个有序数组中查找具体的某个数字n。

    编写int binary_search (int x, int v[], int n);

    功能:在v [0] <= v [1] <= v [2] <= …. <= v [n-1]的数组中查找x.

    题目大概的意思就是说这是一串有序的数组,我们编写代码完成以下功能:如果输入的数字在数组中,就输出找到了并输出下标,如果输入的数字不在数组中则输出找不到。

    下面看解法:

    解法一: 挨个遍历

    #include <stdio.h>
    int main()
    {
        int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
        //查找7
      www.cppcns.com  //遍历 0 ~ sz - 1
        int sz = sizeof(arr) / sizeof(arr[0]);
        int i = 0;
        int flag = 0;//0表示没有找到
        for (i = 0; i < sz; i++)
        {
            if(7 == arr[i])
            {
                flag = 1;
                break;
            }
        }
        if (1 == flag)
            printf("找到了,下标是:%d\n", i);
        else
            printf("没找到\n");
        return 0;
    }
    

    博主这里的代码为了让大家可以看的更清楚,所以没有写成输入的模式,而是直接想要查找7。

    这是万能的方法,http://www.cppcns.com就挨个遍历,有就是有,没有就是没有,属实牛批,但缺点是太费时间,如果要查找1 - 10000000中的10000000,那未免也太久了,既然这样的数组是一串有序的数组,不妨我们可以试试二分查找/折半查找。

    方法二:折半查找/二分查找(仅适用于有序查找)

    方法分析:

    下面分析一下折半查找是怎么实现的,比如我们的数组是1 - 10,想要查找的数是7,那我们知道下标为0的数组对于1,下标为9的数组对于10,那我们则应该先找到中间下标对应的元素arr[mid],让他www.cppcns.com和7比较,如果比7大,则将最右边的下标赋值为mid - 1,反之,则将最左边下标赋值为mid + 1,这PhzetSuYFq样循环往复无限逼近要查找的数,每次排查一半,直到arr[mid] == 7,就找到了,如果直到最左下标和最右下标重合之后都找不到,那这个数一定不在这个有序数组内。

    下面我们看代码是怎么写的:

    代码实现:

    #include <stdio.h>
    int main()
    {
        int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
        //查找7
        //0 ~ sz - 1
        int sz = sizeof (arr) / sizeof (arr[0]);
        int left = 0;
        int http://www.cppcns.comright = sz - 1;
        int mid = 0;
        int k = 7;//要查找的元素
        int flag = 0;
        while(left <= right) // 即使是 left == right,也有一个元素需要被查找
        {
            //求中间元素下标
            mid = (left + right) / 2; // 每一次二分查找都要求出新的中间元素下标
            if(arr[mid] < k)
            {
                left = mid + 1;
            }
            else if (arr[mid] > k)
            {
                right = mid - 1;
            }
            else
            {
                //找到了
                flag = 1;
                break;
            }
        }
        if (1 == flag)
            printf("找到了,下标是:%d\n", mid);
        else
            printf("找不到\n");
        return 0;
    }
    

    虽然折半查找看起来代码比遍历查找多一些,但其实中间省了非常多计算机计算的时间,非常好用~~

    总结

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

    扫码领视频副本.gif

    0

    精彩评论

    暂无评论...
    验证码 换一张
    取 消