精华内容
下载资源
问答
  • 内含acm折半查找例题、源代码、测试数据。
  • 直接插入排序与折半查找 代码 #include<stdio.h> #define N 20 int BSearch(int a[],int x,int low,int high);//折半查找 //在升序序列中插入元素x //直接插入排序:将一个记录插入到已排好序的有序表中 ...

    【c语言基本例题总结】

    问题描述

    直接插入排序与折半查找

    代码

    #include<stdio.h>
    #define N 20
    int BSearch(int a[],int x,int low,int high);//折半查找 
    //在升序序列中插入元素x
    
    //直接插入排序:将一个记录插入到已排好序的有序表中 
    int main(void){
    	int i,x;
    	int a[N]={1,3,5,7,9,11,13,15,17,19},n=10; 
    	printf("输入新元素:");
    	scanf("%d",&x);
    	//从最后 一个元素开始,比x大的依次后移
    	for(i=n-1;i>=0;i--){
    		if(a[i]>x){
    			a[i+1]=a[i];//将a[i]后移一位,即将a[i]的值存入a[i+1]
    		}else{
    			break;
    		} 
    	} 
    	a[i+1]=x;
    	printf("插入新元素后的数组:\n");
    	for(i=0;i<=n;i++){
    		printf("%d ",a[i]);
    	}
    	printf("\n");
    	//二分查找
    	printf("在整数序列中搜索给定值x,输入x:");
    	scanf("%d",&x);
    	printf("在整数序列中搜索给定值x的位置%d\n", BSearch(a,x,0,n)); 
    	return 0;
    	
    }
    //折半搜索给定值x的位置
    int BSearch(int a[],int x,int low,int high){
    	if(low>high){
    		return -1;
    	} 
    	else{
    		int mid=(low+high)/2;
    		if(x==a[mid]) return mid;
    		if(x<a[mid]){
    			return BSearch(a,x,low,mid-1);
    		}else{
    			return BSearch(a,x,mid+1,high);
    		}
    	}
    }
    

    运行结果

    在这里插入图片描述

    展开全文
  • 折半查找实例

    2018-10-17 21:26:16
    该程序是一个折半查找的一个具体的例子,其中有对数组的冒泡排序,以及随机数组的产生。
  • 折半查找

    2019-09-24 13:43:09
    算法:不断的从中间拿其中的数字,去与要找的数字比较,从而缩小范围,达到折半查找的好处。 例题如下: 题目: 实现折半查找。要求查找给定的值在数据表中相应的存储位置。本题目假定输入元素均按非降序输入。 ...

     算法:不断的从中间拿其中的数字,去与要找的数字比较,从而缩小范围,达到折半查找的好处。

    例题如下:

    题目:

    实现折半查找。要求查找给定的值在数据表中相应的存储位置。本题目假定输入元素均按非降序输入。

    输入:

    输入包含若干个测试用例,第一行为测试用例个数k。每个测试用例占3行,其中第一行为元素个数n,第二行为n个元素值,即数据表中的元素,第三行为需要查找的元素。

    输出:

    对每一测试用例,分别用一行输出两个值,分别表示相应的位置和查找次数,用空格隔开。如果查找不成功,则位置表0表示。

    例题输出:

    1
    5
    1 2 4 7 9
    4

    例题输出:

    3 1


    样码如下:
     
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    
    using namespace std;
    int vis[10010];
    int m,cnt;
    int maxn;
    
    int cmp()
    {
        int i = 1,j=m;
        while(i<=j)
        {
            int min = (i+j)/2;
            maxn =maxn+1;
            if(vis[min]==cnt)
            {
                return min;
            }
            if(vis[min]>cnt)
                j = min-1;
            else
                i = min+1;
        }
        return 0;
    }
    
    int main()
    {
        int T;
        scanf("%d",&T);
        while(T--)
        {
            maxn =0;
            scanf("%d",&m);
            for(int i=1; i<=m; i++)
            {
                scanf("%d",&vis[i]);
            }
            sort(vis+1,vis+1+m);
            maxn = 0;
            scanf("%d",&cnt);
            int pos = cmp();
            printf("%d %d\n",pos,maxn);
        }
        return 0;
    }

    转载于:https://www.cnblogs.com/new-zjw/p/8540964.html

    展开全文
  • 数组_例题折半查找

    千次阅读 2014-04-14 10:57:42
    /*折半查找法!*/# include # define N 10int main(void){ int i, num; int data[] = {13,15,23,29,30,31,38,45,56,69}; //在数组中存放10个整数; int low=0, high=N-1, mid;//定义数组中最低、最高及中间元素; ...

    /*
    折半查找法!
    */
    # include <stdio.h>
    # define N 10

    int main(void)
    {
    int i, num;
    int data[] = {13,15,23,29,30,31,38,45,56,69}; //在数组中存放10个整数;
    int low=0, high=N-1, mid;//定义数组中最低、最高及中间元素;

    printf("Please input a num:\n");
    scanf("%d", &num); //输入查找的数字;

    for(i=0; i<N; ++i)
    {
    if(i%5 == 0 && i!=0)
    printf("\n"); //每显示5行换行,以排列整齐;
    printf("data[%d]=%d ", i, data[i]); //输出赋值好的数组内的所有元素;
    mid = (low+high)/2;//计算出中间值;
    }
    while(low<=high)
    {
    mid = (low+high)/2;//计算中间值,第一次为(0+9)/2=4,data[4]为第五个数字30;
    if(num == data[mid])
    {
    printf("\nFind %d, It is data[%d]!", num, mid);
    break;
    }
    else if(num > data[mid])
    low = mid+1; //注意:是mid+1而非low+1;
    else
    high = mid-1;


    }
    if(low>high) //无该数字,查找失败。
    printf("\n%d is not in data[]", num);
    printf("\nlow = %d, high = %d", low, high);
    putchar('\n');

    return 0;
    }



    展开全文
  • 折半查找

    千次阅读 多人点赞 2020-03-19 20:43:24
    文章目录折半查找法摘要概述引申解题步骤算法代码实现 折半查找法 摘要 折半查找法是效率较高的一种查找方法。假设有已经按照从小到大的顺序排列好的五个整数a0~a4,要查找的数是X,其基本思想是: 设查找数据的范围...

    折半查找法

    摘要

    折半查找法是效率较高的一种查找方法。假设有已经按照从小到大的顺序排列好的五个整数a0~a4,要查找的数是X,其基本思想是: 设查找数据的范围下限为l=1,上限为h=5,求中点m=(l+h)/2,用X与中点元素am比较,若X等于am,即找到,停止查找;否则,若X大于am,替换下限l=m+1,到下半段继续查找;若X小于am,换上限h=m-1,到上半段继续查找;如此重复前面的过程直到找到或者l>h为止。如果l>h,说明没有此数,打印找不到信息,程序结束。

    概述

    该方法是查找的范围不断缩小一半,所以查找效率较高。
    三角形加倍折半法 加倍折半法的关键是如何“加倍”、“折半”。那么“加倍”、“折半”的方法又是什么呢?传统的“加倍”的方法,是将线段延长一倍;传统的“折半”的方法,是取线段的中点。岂不知,“三角形中位线定理”、“直角三角形斜边上的中线等于斜边的一半”、“等腰三角形的三线合一性质”、“平行线等分线段定理”……均有“加倍、折半”的功用。也就是说“加倍”“折半”的方法是众多的、丰富的。而这些的方法基本上都是来自上述的一些重要的定理。
    例1 已知:△ABC中,AB=AC,延长AB到D,使DB=AB,E是AB的中点。求证:CD=2CE
    思路一:延长CE到F1,使EF1=CE,即用
    延长的方法将CE扩大一倍为CF1,证CF1=CD
    思路二:取CD的中点,即用“取中点”的方法将CD缩小一半为CF2,证CF2=CE。
    以上为“传统”的加倍折半法,引申后则有:
    思路三:抓住E为AB中点这一特点,作△ABF3,使CE为该三角形的中位线(过A作AF3∥CE,交BC的延长线于F3),即用三角形中位线定理将CE扩大一倍为AF3,证AF3=CD
    思路四:抓住B为AD中点这一特点,作△ADC以CD边为底边的中位线(过B作BF4∥CD,交AC于F4),即:用三角形中位线定理将CD缩小一半为BF4,证BF4=CE

    引申

    对三角形加倍折半法“用途”的引申
    传统的加倍折半法主要应用于线段(或角)倍半关系的证明。随着“方法”的引申,其功能也随之得到了增强。特别是完全领会了加倍折半法的基本思想后,许多疑难问题就会迎刃而解。它的用途远远超出了原先的范围,几乎适用于所有含“2”的类型题。下面,分“结论中含有2”和“题设中含有2”两中情况作简单的介绍。
    1、加倍折半法来解“结论中含有2”的类型题,实际上就是“分析法”的一种具体应用。“加倍折半法”在此起的作用,也可称之为“解题技巧”。例1属于该种类型的“传统”例题,下面举几个引申后的例子。
    例2 已知:△ABC中,D是BC上的中点,F是AD上的任意一点,延长CF交AB于E。求证:AF:DF=2AE:BE
    思路:本题的难点是如何除去比例式中的“2”
    方法一:将AE或DF“加倍”,由于D是BC的中点,
    过点B作BG∥DF,交CE的延长线于G,则用三角形中位线定理将DF“扩大一倍”为BG。这样,原题就有效的转化为证明AF:BG=AE:BE。
    方法二:是将AF或BE“折半”,由于D是BC的中点,过点D作DH∥AB,交CE于GH,则用三角形中位线的定理将BE“缩小一半”为DH。这样,原题就有效的转化为证明AF:DF=AE:DH。
    2、用加倍折半法来解“题设中含有2”的类型题,实际上就是“综合法”的一种具体的应用。“加倍折半法”在此起的作用,可称之为“解题经验”。
    例3 已知:△ABC中,AD是高线,∠ABC=2∠ACB。求证:CD=AB+BD
    思路:该题属于“截长补短法”的习题,
    折半查找法
    但由于已知条件中有角的倍半关系,因
    而用“加倍折半法”的思路也可以解决。
    思路一:延长DB到E1,使BE1=BA(造等腰三角形将∠ABC“折半“为E1),则∠E1=∠C,AE1=AC,CD=DE1,故CD=AB+BD
    思路二:作∠CAE2,使∠CAE2=∠C(造等腰三角形将∠C“加倍”为∠AE2B),则∠AE2B=∠ABC,AE2=E2C=AB,BD=DE2,故CD=AB+BD。

    在这里插入图片描述

    解题步骤

    1.定义3个用来记录索引值的变量,变量min记录当前范围最小索引值,初始值为0;变量max记录当前范围最大索引值,初始值为数组长度-1;变量mid记录当前当前范围最中间元素的索引值,初始值为(min+max) / 2
    2.使用循环,判断当前范围下,最中间元素值与指定查找的数值是否相等
    若相等,结束循环,返回当前范围最中间元素的索引值mid
    若不相等,根据比较结果,缩小查询范围为上一次查询范围的一般
    中间元素值 比 要查询的数值大,说明要查询的数值在当前范围的最小索引位置与中间索引位置之间,此时,更新查询范围为:
    范围最大索引值 = 上一次中间索引位置 -1;
    中间元素值 比 要查询的数值小,说明要查询的数值在当前范围的最大索引位置与中间索引位置之间,此时,更新查询范围为:
    范围最小索引值 = 上一次中间索引位置 +1;
    在新的查询范围中,更新中间元素值的位置,再次使用最中间元素值与指定查找的数值是否相等。
    中间索引值 = (范围最小索引值 +范围最大索引值) / 2;
    3.每次查询范围缩小一半后,使用if语句判断,查询范围是否小于0个元素,若小于0个元素,则说明指定数值没有查询到,返回索引值-1。

    算法代码实现

    
    int search(int* p, int number, int under, int top)
    {
        int mind = (under + top) / 2;  //二分法查找    
    
        if (mind < under || mind > top)
        {
            return 0;
        }
        else if (p[mind] < number)   
        {
            return search(p, number, mind + 1, top);
        }
        else if (p[mind] > number)
        {
            return search(p, number, under, mind - 1);
        }
        else return mind+1;
    }
    
    展开全文
  • C语言简单实现折半查找

    万次阅读 多人点赞 2018-08-16 08:27:12
    折半查找,又称作二分查找。这个查找的算法的特点,就是,要求数据要是有序的。 1 ,存储结构一定是顺序存储 2 ,关键字大小必须有序排列 算法思想:折半查找只能在有序数列中进行,将待查找的数据与有序数列...
  • 折半查找 解题报告

    2020-04-23 10:03:41
    折半查找 解题报告 折半查找是查找方法中的一种,常用的查找方法还有遍历查找。 折半查找运用了二分的思想,也可称为二分查找。其思想是在有序数组a(必须是有序的,从小到大或从大到小都可以)查找指定元素k,则将...
  • 折半查找算法

    千次阅读 2021-01-15 11:21:30
      答案:猜中间数 代码实现:      二分查找应用:  寻找一个数、寻找左侧边界、寻找右侧边界 1)代码框架:  二分查找法实质上是不断地将有序数据集进行对半分割,并检查每个分区的中间元素。时间复杂度为O...
  • 对于折半查找有序表里面其中的一个元素的话我们需要注意以下几点 &gt;首先我们需要将表中的元素从小到大排序,由于题目中已经说了是有序表所以我们不需要将这些元素排序(切记这一步很重要) &gt;由于是...
  • 二分法(折半查找

    2021-03-26 13:56:23
    二分法查找数据,也称折半查找,更高效率的查询数组中的某个数据。
  • 如果从文件中读取的数据记录的关键字是有序排列的,则可以用一种效率更高的查找算法来查找文件中的记录,这就是折半查找法,又称作为二分查找。 折半查找的思想是:减小查找序列的长度,分而地进行关键字的查找,它...
  • 折半查找法问题

    千次阅读 2018-09-15 14:08:18
    有15个数存放在一个数组中,输入一个数,要求用折半查找法找出该数是数组中第几个元素值。如果该数不在数组中,则打印出“无此数”。 2.编程分析 首先要把15个数排序,这里选择的是选择排序法,然后用折半查找...
  • Java算法之折半查找

    2020-04-26 10:43:49
    Java 算法之折半查找法 算法介绍 折半查找法要求线性表是有序的,即表中记录按关键字有序(假设是递增有序的)。 折半查找的基本思路:设 R[low, ···, high] 是当前的查找区间,首先确定该区间的中间位置 mid = ...
  • C语言习题 折半查找

    千次阅读 2017-08-11 14:04:59
    2413: C语言习题 折半查找 Time Limit: 1 Sec Memory Limit: 128 MB Submit: 1829 Solved: 687 [Submit][Status][Web Board] Description 有n个数(n 要求: 编写两个函数input和binbearch分别实现...
  • 折半查找法(二分法)流程图

    千次阅读 2020-02-08 20:03:23
    折半查找法漂亮的流程图 1.n维有序数组通过折半查找法查找数m,若查到则输出查找数字index,若没查到,则输出”not be found“。
  • (我在我的基础算法代码共享模块中放出过折半查找的代码模板及例题,有兴趣的朋友可以前往自行查看)它的前提是线性表中的记录必须是有序的(通常是升序),且线性表必须采取顺序存储(即使用数组存储)。折半查找的...
  • 顺序查找法 概述:从表的一端开始,逐个进行记录的关键字和给定值的比较,若找到一个记录的关键字与给定值相等,则查找成功;若整个表中的记录均比较过,...折半查找法 概述:又称为二分查找法,查找过程令处于中间位
  • 折半查找算法是对于有序的序列而言的,每次查找后折半,大概缩短了一半的查找区间,是一种效率较高的查找算法。 要求: list必须是顺序结构,且按照关键词大小进行有序排列。 思路: 在有序序列中查找元素,每次取...
  • 二分查找算法又叫折半查找算法,算法的效率是很高的,这点毋庸置疑,但其有自己特有的使用范围,仅可以查找有序的数列,对于无序、乱序的数列是不适用的 方法思维: 每次将查找的数列进行折半拆分,也就是一分为二的...
  • 折半查找法是数据结构与算法的应用中相对重要的一个查找方法。还可以通过数学方法计算其时间复杂度。
  • 折半查找法是效率较高的一种查找方法。假设有已经按照从小到大的顺序排列好的五个整数a0~a4,要查找的数是X, 其基本思想是: 设查找数据的范围下限为l=0,上限为h=4,求中点m=(l+h)/2,用X与中点元素am比较,若X...
  • 七大查找算法:https://www.cnblogs.com/zhang-qc/p/8745153.html ... 关于查找表: 上面,静态查找表,找的过程中不改变表...静态查找表,对确定的数据元素关系的表查找,不一定是线性表。 关于查找: 上面,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 850
精华内容 340
关键字:

折半查找例题