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

目录
  • 题目
    • 解法一： 挨个遍历
    • 方法二：折半查找/二分查找（仅适用于有序查找）
  • 总结

题目

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

在一个有序数组中查找具体的某个数字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
    //遍历 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，就找到了，如果直到最左下标和最右下标重合之后都找不到，那这个数一定不在这个有序数组内。

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

代码实现：

#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;
}

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

总结

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

赞 (0)

相关推荐

  • C语言二叉树常见操作详解【前序,中序,后序,层次遍历及非递归查找,统计个数,比较,求深度】

    C语言二叉树常见操作详解【前序,中序,后序,层次遍历及非递归查找,统计个数,比较,求深度】

    本文实例讲述了C语言二叉树常见操作.分享给大家供大家参考,具体如下: 一.基本概念 每个结点最多有两棵子树,左子树和右子树,次序不可以颠倒. 性质: 1.非空二叉树的第n层上至多有2^(n-1)个元素. 2.深度为h的二叉树至多有2^h-1个结点. 满二叉树:所有终端都在同一层次,且非终端结点的度数为2. 在满二叉树中若其深度为h,则其所包含的结点数必为2^h-1. 完全二叉树:除了最大的层次即成为一颗满二叉树且层次最大那层所有的结点均向左靠齐,即集中在左面的位置上,不能有空位置. 对于完全二叉

  • C语言实现顺序表的顺序查找和折半查找

    本文实例为大家分享了C语言实现顺序表的顺序查找和折半查找的具体代码,供大家参考,具体内容如下 顺序查找: #include <iostream> using namespace std; int SeqSearch(int r[],int n,int k) { r[0]=k;//下标0用作哨兵存放要查询的数 int i=n; while(r[i]!=k)//不用判断下标i是否越界 { i--; } return i; } int main() { int n; cout<<&quo

  • C语言基础之二分查找知识最全汇总

    C语言基础之二分查找知识最全汇总

    一.前言 在自学二分查找的过程中我想到了一些变化问题,有的自己就慢慢理解了,有的在网上找到了答案,奈何没有找到想要的总结归纳.我就斗胆自己写了一篇,号称史上最全.希望和我一样的伙伴可以少走一点弯路. 二分查找凭借其低时间复杂度O(log(n))成为了各个蒟蒻的入门知识,但是其衍生出的各种题目相较原题目而言就没有那么容易求解,以下借用c语言实现二分查找算法及其衍生.二分查找仅适用于事先已经排好序的顺序表.其基本思路就是每次取中间数,如果中间数大于所求数就向上查找,反之向下. 二.原始二分查找 1.

  • C语言实现折半查找法（二分法）

    折半查找法也叫做二分查找,顾名思义,就是把数据分成两半,再判断所查找的key在哪一半中,再重复上述步骤知道找到目标key; 注意:折半查找法仅适用于对已有顺序的数组.数据进行操作!!! 很显然,折半查找法相对于其他查找方法例如顺序查找法效率要高很多: 下面我们来实际操作一下,了解二分查找的奥义. 例如:要在数组arr[]={8,7,9,6,4,1,2,5,3,10,11};中查找key=7的位置:首先,我们要先将数组arr中的数据成员进行排序.arr[]={1,2,3,4,5,6,7,8,9,1

  • c语言实现找最大值最小值位置查找

    找最大值最小值位置 从键盘任意输入10个整数,计算并输出最大值和最小值及其它们在数组中的下标位置. 程序运行结果示例1: Input 10 numbers:1 2 3 4 5 6 7 8 9 10 max=10,pos=9 min=1,pos=0 程序运行结果示例2: Input 10 numbers:2 4 5 6 8 10 1 3 5 7 9 max=10,pos=5 min=1,pos=6 程序: #include <stdio.h> int FindMax(int a[], int n

  • C语言算法练习之折半查找的实现

    C语言算法练习之折半查找的实现

    目录 1. 题目描述 2. 问题分析 3. 算法设计 4. 动图演示 5. 代码实现 6.知识点补充 continue 语句 break 语句 continue语句 和 break语句的区别 7. 问题拓展 1. 题目描述 N 个有序整数数列已放在一维数组中,利用二分查找法查找整数 m 在数组中的位置. 若找到,则输出其下标值:反之,则输出 “ Not be found!”. 2. 问题分析 二分查找法(也叫折半查找)其本质是分治算法的一种. 所谓分治算法是指的分而治之,即将较大规模的问题分解成

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

    目录 题目 解法一: 挨个遍历 方法二:折半查找/二分查找(仅适用于有序查找) 总结 题目 首先我们来把题目瞅一眼: 在一个有序数组中查找具体的某个数字n. 编写int binary_search (int x, int v[], int n); 功能:在v [0] <= v [1] <= v [2] <= -. <= v [n-1]的数组中查找x. 题目大概的意思就是说这是一串有序的数组,我们编写代码完成以下功能:如果输入的数字在数组中,就输出找到了并输出下标,如果输入的数字不在

  • C语言使用stdlib.h库函数的二分查找和快速排序的实现代码

    快速排序: 复制代码 代码如下: #include <stdlib.h>#include <stdio.h>#include <string.h> #define LENGTH(x) sizeof(x)/sizeof(x[0]) /**输出数组元素*\param arr:指向数组的指针*\param len:数组元素的个数*/void print(char (*arr)[10],int len){    int i;    for (i=0;i<len;i++) 

  • PHP有序表查找之二分查找（折半查找）算法示例

    本文实例讲述了PHP有序表查找之二分查找(折半查找)算法.分享给大家供大家参考,具体如下: 简介: 二分查找技术,又称为折半查找.它的前提是线性表中的记录必须是关键码有序(通常从小到达有序),线性表必须采用顺序存储. 基本思想: 在有序表中,取中间记录作为比较对象,若给定值与中间记录的关键字相等,则查找成功:若给定值小于中间记录的关键字,则在中间记录的左半区继续查找:若给定值大于中间记录的关键字,则在中间记录的右半区继续查找.不断重复上述过程,直到查找成功,或所有查找区域无记录,查找失败为止.

  • C语言巧用二分查找实现猜数游戏

    C语言巧用二分查找实现猜数游戏

    目录 (壹)二分查找   1.1  何为二分查找   1.2  二分查找的原理   1.3  查找条件   1.4  代码实现 1.4.1  初始化数据 1.4.2  核心函数 (贰)猜数字游戏   2.1  菜单初始化   2.2  核心函数   2.3  main函数   2.4  总代码 文章Gitee仓库:文章源代码 (壹)二分查找   1.1  何为二分查找 折半查找,也称二分查找,在某些情况下相比于顺序查找,使用折半查找算法的效率更高.但是该算法的使用的前提是静态查找表中的数据必须是

  • 使用PHP实现二分查找算法代码分享

    第一种方法: [二分查找要求]:1.必须采用顺序存储结构 2.必须按关键字大小有序排列. [优缺点]折半查找法的优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难.因此,折半查找方法适用于不经常变动而查找频繁的有序列表. [算法思想]首先,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功:否则利用中间位置记录将表分成前.后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表. 复制代码 代码如下: <?

  • Java实现查找算法的示例代码(二分查找、插值查找、斐波那契查找)

    Java实现查找算法的示例代码(二分查找、插值查找、斐波那契查找)

    目录 1.查找概述 2.顺序查找 3.二分查找 3.1 二分查找概述 3.2 二分查找实现 4.插值查找 4.1 插值查找概述 4.2 插值查找实现 5.斐波那契查找 5.1 斐波那契查找概述 5.2 斐波那契查找实现 5.3 总结 1.查找概述 查找表: 所有需要被查的数据所在的集合,我们给它一个统称叫查找表.查找表(Search Table)是由同一类型的数据元素(或记录)构成的集合. 查找(Searching): 根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素(或记录).

  • 详解C语言中二分查找的运用技巧

    详解C语言中二分查找的运用技巧

    目录 基础的二分查 查找左侧边界 查找右侧边界 二分查找问题分析 实例1: 爱吃香蕉的珂珂 实例2:运送包裹 前篇文章聊到了二分查找的基础以及细节的处理问题,主要介绍了 查找和目标值相等的元素.查找第一个和目标值相等的元素.查找最后一个和目标值相等的元素 三种情况. 这些情况都适用于有序数组中查找指定元素 这个基本的场景,但实际应用中可能不会这么直接,甚至看了题目之后,都不会想到可以用二分查找算法来解决 . 本文就来分析下二分查找在实际中的应用,通过分析几个应用二分查找的实例,总结下能使用二分查

  • C语言通过二分查找实现猜数字游戏

    目录 二分查找 二分查找的思想 二分查找的条件 二分查找的实现过程 代码举例 猜数字游戏 游戏说明 猜数字游戏思想 代码实现 整体代码演示 二分查找 题目: 在一个有序数组中查找具体的某个数字n. 首先我们先定义一个1···10的数组 ,如果7为我们要查找的数字,编写代码如下 #include <stdio.h> int main() { int arr[] = { 1,2,3,4,5,6,7,8,9,10 }; // 下标 0 1 2 3 4 5 6 7 8 9 int k = 7;//k是

随机推荐