服务器之家:专注于服务器技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|Java教程|ASP教程|编程技术|正则表达式|C/C++|IOS|C#|Swift|Android|VB|R语言|JavaScript|易语言|vb.net|

服务器之家 - 编程语言 - C/C++ - C语言算法--有序查找(折半查找/二分查找)

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

2021-12-22 14:27Aaronskr C/C++

我们知道无序查找只能靠遍历,如果有序查找我们还挨个去遍历,未免太浪费时间,所以这里我们会用到不一样的方法,希望能给你带来帮助

题目

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

在一个有序数组中查找具体的某个数字n。
编写int binary_search (int x, int v[], int n);
功能:在v [0] <= v [1] <= v [2] <= …. <= v [n-1]的数组中查找x.

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

下面看解法:

解法一: 挨个遍历

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#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 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。

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

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

方法分析:

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

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

代码实现:

?
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
#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 right = 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;
}

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

总结

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

原文链接:https://blog.csdn.net/Aaron_skr/article/details/119873642

延伸 · 阅读

精彩推荐
  • C/C++C语言实现电脑关机程序

    C语言实现电脑关机程序

    这篇文章主要为大家详细介绍了C语言实现电脑关机程序,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...

    xiaocaidayong8482021-08-20
  • C/C++学习C++编程的必备软件

    学习C++编程的必备软件

    本文给大家分享的是作者在学习使用C++进行编程的时候所用到的一些常用的软件,这里推荐给大家...

    谢恩铭10102021-05-08
  • C/C++c++ 单线程实现同时监听多个端口

    c++ 单线程实现同时监听多个端口

    这篇文章主要介绍了c++ 单线程实现同时监听多个端口的方法,帮助大家更好的理解和学习使用c++,感兴趣的朋友可以了解下...

    源之缘11542021-10-27
  • C/C++C/C++经典实例之模拟计算器示例代码

    C/C++经典实例之模拟计算器示例代码

    最近在看到的一个需求,本以为比较简单,但花了不少时间,所以下面这篇文章主要给大家介绍了关于C/C++经典实例之模拟计算器的相关资料,文中通过示...

    jia150610152021-06-07
  • C/C++C++之重载 重定义与重写用法详解

    C++之重载 重定义与重写用法详解

    这篇文章主要介绍了C++之重载 重定义与重写用法详解,本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下...

    青山的青6062022-01-04
  • C/C++C语言中炫酷的文件操作实例详解

    C语言中炫酷的文件操作实例详解

    内存中的数据都是暂时的,当程序结束时,它们都将丢失,为了永久性的保存大量的数据,C语言提供了对文件的操作,这篇文章主要给大家介绍了关于C语言中文件...

    针眼_6702022-01-24
  • C/C++详解c语言中的 strcpy和strncpy字符串函数使用

    详解c语言中的 strcpy和strncpy字符串函数使用

    strcpy 和strcnpy函数是字符串复制函数。接下来通过本文给大家介绍c语言中的strcpy和strncpy字符串函数使用,感兴趣的朋友跟随小编要求看看吧...

    spring-go5642021-07-02
  • C/C++深入理解goto语句的替代实现方式分析

    深入理解goto语句的替代实现方式分析

    本篇文章是对goto语句的替代实现方式进行了详细的分析介绍,需要的朋友参考下...

    C语言教程网7342020-12-03