精华内容
下载资源
问答
  • 折半查找的C语言程序,可用 基于C语言的程序 利用顺序表,学习数据结构时会有用
  • 折半查找的应用前提是数组是一个有序数组。比较数组中间值和查找值的大小关系,然后确定下一步的查找范围,逐次缩小。折半查找的时间复杂度为O(log2(n)),是一种效率很高的查找方式。 程序实现 #include <stdio.h...

    折半查找的应用前提是数组是一个有序数组。比较数组中间值和查找值的大小关系,然后确定下一步的查找范围,逐次缩小。折半查找的时间复杂度为O(log2(n)),是一种效率很高的查找方式。
    程序实现

    #include <stdio.h>
    #include <math.h>
    
    int search(int key, int a[], int len)
    {
        int left = 0, right = len-1;
        int mid = 0;
        int res = -1;
        while( right > left )
        {
            mid = (left+right)/2;
            if( a[mid] == key)
            {
                res = mid;
                break;
            }
            else if( a[mid]>key )
            {
                right = mid-1;
            }
            else
            {
                left = mid+1;
            }
        }
        
        return res;
    }
    
    
    int main()
    {
        int a[] = {2,4,5,7,9,12,14,16,35,79};
        int len = sizeof(a)/sizeof(a[0]);
        int x;
        printf("请输入要查找的数:");
        scanf("%d",&x);
        int r = search(x,a,len);
        if(r!=-1)
        {
            printf("%d所在的位置为:%d\n",x,r);
        }
        else
        {
            printf("这里没有要查找的数。\n");
        }
        return 0;
    }
    

    运行结果
    在这里插入图片描述
    在这里插入图片描述
    前面说过折半查找的时间复杂度为O(log2(n)),据此我们也可以得到一些常见的说法。

    10 3
    100 7
    1,000 10
    1,000,000 20
    1,000,000,000 30

    也即是说在100个数中查找,最多7次就可以找到;在1000个数中查找,最多10次就可以找到。

    展开全文
  • //查找函数 int Search_Bin(SSTable *ST,int number) { int low=1,high=ST->length; int mid; while(low) { mid=(low+high)/2; if(EQ(ST->elem[mid].number,number)) return mid; else if(LT(number,ST->elem[mid]....
  • 折半(二分)查找算法C语言程序,首先借助于快速排序算法对数组进行从小到大排序,然后折半进行查找,直到找到相应数字为止。
  • C语言折半查找的程序编写

    千次阅读 2017-04-08 16:34:52
    # include<stdio.h>int binary_search(int arr[], int key, int left, int right) { while (left ) { int mid = left + ((right - left) >> 1); if (key > arr[mid]) {
    # include<stdio.h>
    
    int binary_search(int arr[], int key, int left, int right)
    {
        while (left <= right)
        {
            int mid = left + ((right - left) >> 1);
            if (key > arr[mid])
            {
                left = mid + 1;
            }
            else if (key < arr[mid])
            {
                right = mid - 1;
            }
            else
            {
                return mid;
            }
        }
        return -1;
    }
    
    int main()
    {
        int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        int key =9;
        int ret = binary_search(arr, key,0, 9);
        if (ret == -1)
        {
            printf("找不到\n");
        }
        else
        {
            printf("找到了:%d\n", ret);
        }
        return 0;
        }
    展开全文
  • 有一个数组 v 已经按升序...解决这个问题的一个普遍方法是折半查找。下面是程序:#include int binsearch(int x, int v[], int n);main(){int i, result, n;int wait;int x = 17;// 需要查找的数值int v[19]; // ...

    有一个数组 v 已经按升序排列了,数组 v 有 n=20 个元素。数组中有个元素 x,如何知道 x 位于该数组的第几位呢?

    解决这个问题的一个普遍方法是折半查找。下面是程序:

    #include

    int binsearch(int x, int v[], int n);

    main()

    {

    int i, result, n;

    int wait;

    int x = 17;// 需要查找的数值

    int v[19]; // 定义一个数组

    // 给数组赋值

    for(i = 0; i < 20; ++i)

    v[i] = i;

    /**

    for(i = 0; i < 20; ++i)

    printf("%d \n", v[i]);

    */

    n = 20;

    result = binsearch(x, v, n);

    printf("%d", result);

    scanf("%d", &wait);

    }

    int binsearch(int x, int v[], int n)

    {

    int low, high, mid;

    low = 0;

    high = n - 1;

    while (low <= high)

    {

    mid = (low + high) / 2;

    if(x < v[mid])

    high = mid - 1;

    else if (x > v[mid])

    low = mid + 1;

    else

    return mid;

    // 看看循环执行了多少次

    printf("mid = %d, low = %d, high = %d \n", mid, low, high);

    }

    return -1;

    }

    思路很简单:首先将输入值 x 与数组 v 的中间元素比较,如果 x 小于中间的元素,则将 high 值设为 中间元素-1,同理,若 x 大于中间元素,则将中间元素 + 1作为 low,再在low 与 high之间进行查找。

    展开全文
  • 程序输出查找成功与否,以及成功时关键字在数组中位置。例如,在有序表 11、13、18、 28、39、56、69、89、98、122 中査找关键字为 89 元素。 实现过程: (1)自定义函数 binary_search(),实现二分査找。 ...

    本实例采用二分查找法查找特定关键字的元素。要求用户输入数组长度,也就是有序表的数据长度,并输入数组元素和査找的关键字。

    程序输出查找成功与否,以及成功时关键字在数组中的位置。例如,在有序表 11、13、18、 28、39、56、69、89、98、122 中査找关键字为 89 的元素。

     

    实现过程:

        (1) 自定义函数 binary_search(),实现二分査找。

        (2) main() 函数作为程序的入口函数。

     

    程序代码如下:

    #include <stdio.h>
    
    int binary_search(int key,int a[],int n) //自定义函数binary_search()
    
    {
    
        int low,high,mid,count=0,count1=0;
    
        low=0;
    
        high=n-1;
    
        while(low<high)    //査找范围不为0时执行循环体语句
    
        {
    
            count++;    //count记录査找次数
    
            mid=(low+high)/2;    //求中间位置
    
            if(key<a[mid])    //key小于中间值时
    
                high=mid-1;    //确定左子表范围
    
            else if(key>a[mid])    //key 大于中间值时
    
                low=mid+1;    //确定右子表范围
    
            else if(key==a[mid])    //当key等于中间值时,证明查找成功
    
            {
    
                printf("查找成功!\n 查找 %d 次!a[%d]=%d",count,mid,key);    //输出査找次数及所査找元素在数组中的位置
    
                count1++;    //count1记录查找成功次数
    
                break;
    
            }
    
        }
    
        if(count1==0)    //判断是否查找失敗
    
            printf("查找失敗!");    //査找失敗输出no found
    
        return 0;
    
    }
    
    int main()
    
    {
    
        int i,key,a[100],n;
    
        printf("请输入数组的长度:\n");
    
        scanf("%d",&n);    //输入数组元素个数
    
        printf("请输入数组元素:\n");
    
        for(i=0;i<n;i++)
    
            scanf("%d",&a[i]);    //输入有序数列到数组a中
    
        printf("请输入你想查找的元素:\n");
    
        scanf("%d",&key);    //输入要^找的关键字
    
        binary_search(key,a,n);    //调用自定义函数
    
        printf("\n");
    
        return 0;
    
    }

     

    运行结果:

    ————————

    请输入数组的长度:

    10

    请输入数组元素:

    11 13 18 28 39 56 69 89 98 122

    请输入你想查找的元素:

    89

    查找成功!

    查找 2 次!a[7]=89

    ————————

     

    技术要点:

    二分査找就是折半查找,其基本思想是:

    首先选取表中间位置的记录,将其关键字与给定关键字 key 进行比较,若相等,则査找成功;

    若 key 值比该关键字值大,则要找的元素一定在右子表中,则继续对右子表进行折半查找;

    若 key 值比该关键宇值小,则要找的元素一定在左子表中,继续对左子表进行折半査找。

    如此递推,直到査找成功或査找失败(或査找范围为 0)。

    最后,不管你是转行也好,初学也罢,进阶也可,如果你想学编程~

    【值得关注】我的 C/C++编程学习交流俱乐部【点击进入】

    问题答疑,学习交流,技术探讨,还有超多编程资源大全,零基础的视频也超棒~

    展开全文
  • 折半查找(二分法查找) :输出下标值和查找次数 #include<stdio.h> #define N 5 //此处查找五个数,可以自由设定个数 int j=0,flag,mid; //j为查找次数;flag起到了判断是否 //注:因为打算调用一个有返回值...
  • c语言 一维数组折半查找法Problem statement: Write a C program to find the second smallest element in a one dimensional array. 问题陈述:编写C程序以查找一维数组中第二个最小元素。 Example: Type1: ...
  • 数据结构中的折半查找程序C语言描述,数据结构中的折半查找程序C语言描述
  • c语言 一维数组折半查找法Problem statement: Write a C program to find second largest element in a one dimensional array. 问题陈述:编写C程序以查找一维数组中第二大元素。 Example: 例: Input : ...
  • C语言二分查找算法折半查找算法 本实例采用二分查找法查找特定关键字元素要求用户输入数组长度也就是有序表数据长度并输入数组元素和査找关键字程序输出查找成功与否以及成功时关键字在数组中位置例如在有序...
  • c语言 一维数组折半查找法Problem statement: Write a C program to find two smallest elements in a one dimensional array. 问题陈述:编写一个C程序以在一维数组中找到两个最小元素。 Example: Type1: (all ...
  • c语言 一维数组折半查找法Problem statement: Write a C program to find two largest elements in a one dimensional array. 问题陈述:编写一个C程序以在一维数组中找到两个最大元素。 Example: Type1: (all ...
  • 编写一个程序exp9-2.cpp,输出在顺序表(1,2,3,4,5,6,7,8,9,10)中采用折半查找方法查找关键字9过程。 //文件名:exp9-2.cpp #include #define MAXL 100 //定义表中最多记录个数 typedef int KeyType; typedef ...
  • [c语言——]折半查找

    2018-11-01 16:47:45
    2.写代码可以在整型有序数组中查找想要数字,找到了返回下标,找不到返回-1.(折半查找) 3.编写代码模拟三次密码输入场景。 最多能输入三次密码,密码正确,提示“登录成功”,密码错误,可以重新输入,最多...
  • C语言简单实现折半查找

    千次阅读 2013-06-09 15:18:07
     有15个数按由大到小顺序存放在一个数组中,输入一个数,要求用折半查找法找出该数是数组中第几个元素值。如果该数不在数组中,则输出“无此数”。  因以前使用其他高级语言时从未使用过该查询算法 ,苦思了有...
  • 最近学到一个比二分法还要精细一些查找方法:折半查找法 进入正题,1.创建一个数组。2.每次查找前先明确查找范围也就是下限是low,上限是high(显然low大多数人都是这么理解,反正就是定义两个变量,最好让大家...
  • 折半查找的递归算法

    2015-11-02 09:54:24
    折半查找的递归算法,非常实用,可以实现的C语言程序
  • 写代码可以在整型有序数组中查找想要的数字,找到了返回下标,找不到返回-1.(折半查找) 解题思路: 折半查找(二分查找): 前提是数组有序。 假设有一个升序数组arr【10】,要查找的数是to_find,其基本思想...
  • 今天我们写一个选择法排序与折半查找法相结合的程序。主要实现先排序在查找。前面我们已经详细讲过了选择排序法,现在我们来说下折半查找折半查找主要思想是 number与mid比较  mid = (butt+top)/2 ...
  • 找到了返回下标,找不到返回-1.(折半查找) 2.编写代码模拟三次密码输入场景。 最多能输入三次密码,密码正确,提示“登录成功”,密码错误, 可以重新输入,最多输入三次。三次均错,则提示退出程序。 3.编写一个...
  • 写代码可以在整型有序数组中查找想要数字,找到了返回下标,找不到返回-1.(折半查找) 3.编写代码模拟三次密码输入场景。 最多能输入三次密码,密码正确,提示“登录成功”,密码错误,可以重新输入,最多...
  • C语言程序设计与数据结构 第15章 查找与排序 总体要求 掌握查找与排序的基本概念 掌握顺序查找和二分查找的算法 掌握直接插入排序简单选择排序冒泡排序的算法 学习重点 查找的有关算法顺序查找折半查找 常用的排序...
  • 非递归折半查找

    2018-05-23 13:26:48
    非递归查找的简单C语言程序,供初学者参考一下,哈哈。
  • 折半查找法,是一种效率比较高的查找法,该算法对待查找的列表有两个要求:①采用顺序存储结构;②关键字必须按大小有序排列 算法的基本思想是: 将待查找的关键字(记为key)与被查找的表中间位置的关键字进行比较...
  • 掌握模块化编程思想和方法 教学内容8.5-8.7节 是否重难点 经典算法 了解 难点 教学设计 由于课堂教学时间有限这部分内容建议学生线下学习 二分查找算法 二分查找算法也称为折半查找算法其基本思想为在有序表中,...
  • (3) 要求任意输入一个整数,用折半查找法从排好序10个数中找出该数,若存在,在主函数中输出其所处位置,否则,提示未找到。提示:可定义input函数完成10个整数输入,sort函数完成输入数排序,search函数...
  • 第18章 C语言常用算法 本章学习重点 了解起泡排序选择排序及合并排序算法 掌握快速排序算法 掌握折半查找算法 了解二叉树概念及其简单操作 18.1 什么是算法 算法的程序公式 程序 = 数据结构 + 算法 1计算机算法 ...

空空如也

空空如也

1 2 3 4 5
收藏数 91
精华内容 36
关键字:

折半查找的c语言程序

c语言 订阅