精华内容
下载资源
问答
  • 二分(折半查找算法练习 Time Limit: 1000 MS Memory Limit: 32768 K Total Submit: 404 (216 ...在一个有序表中利用二分法查找某个关键字是否存在。 Input 输入为多组数据,每组为两行数据,每组中第一行...

    二分(折半)查找算法练习
    Time Limit: 1000 MS Memory Limit: 32768 K
    Total Submit: 404 (216 users) Total Accepted: 230 (211 users) Special Judge: No
    Description
    在一个有序表中利用二分法查找某个关键字是否存在。
    Input
    输入为多组数据,每组为两行数据,每组中第一行为建立查找的顺序表,第二行是要查找的关键字。
    Output
    若找到关键字,则输出关键字在表中的位置,否则输出0.
    Sample Input
    1 2 3 4 5

    10

    1 2 3 4 5

    5

    Sample Output
    0

    5

    #include<stdio.h>
    #include<stdlib.h>
    typedef int elep;
    #define maxn 1005
    struct sq
    {
        elep *p;
        elep length;
        elep size;
    };
    void insert(sq &l,int x)
    {
        l.p[l.length+1]=x;//插入元素
        l.length++;//刷新表内元素个数
    }
    sq start()
    {
        sq l;
        l.p=(int *)malloc(maxn*sizeof(elep));//开辟空间
        l.length=0;
        l.size=maxn;//设置最大容量
        return l;
    }
    int BinarySearch(sq l ,int n, int key){ 						//折半查找(二分)
    	int low,high,mid;
    	low=1;														//最低下标
    	high=n;														//最高下标
    	while(low<=high){
    		mid=(low+high)/2;										//二分
    		if(key<l.p[mid]){
    			high=mid-1;
    		}else if(key>l.p[mid]){
    			low=mid+1;
    		}else{
    			return mid;
    		}
    	}
    	return 0;
    }
    int main()
    {
        sq l;
        int a,b;
        l=start();
        while(~scanf("%d",&a))
            {
                insert(l,a);
            if(getchar()=='\n') {
            scanf("%d",&b);
            printf("%d\n",BinarySearch(l,l.length,b));
        }}}
    
    
    
    展开全文
  • 折半查找

    千次阅读 多人点赞 2019-04-22 22:52:56
    折半查找也称二分法查找,是在有序数组查找某特定元素的搜索算法。这种方法要求待查找的顺序存储而且必须是有序的。 二、查找过程 首先计算中间的位置,将中间位置处的关键字与查找的关键字进行比较...

    一、定义:
    折半查找也称二分法查找,是一种在有序数组中查找某一特定元素的搜索算法。这种方法要求待查找的表顺序存储而且必须是有序的。
    二、查找过程
    首先计算表中间的位置,将表中间位置处的关键字与查找的关键字进行比较,如果相等,则查找成功;否则利用中间位置将表分为前、后两个子表,如果中间位置的关键字大于查找的关键字,则查找前子表,否则查找后子表。重复上面的过程,直到找到要查找的关键字为止,否则查找失败不存在此关键字。
    例:对{2,5,6,9,17,23,54}中的17进行查找
    在这里插入图片描述

    如图,初始时先让low和high在数据集合的头和尾,中间位置为mid,low=0,high=6.所以mid=(0+6)/2=3,即3位置处,关键字为9不等于17,因为17>9//中间位置的关键字小于要查找的关键字,所以应该在后半子表中。接着再计算后半子表中的中间位置:此时low=mid+1,high=high,则mid=(4+6)/2=5,即5处的关键字为23,23不等于17,且17<23//中间位置的关键字大于要查找的关键字,所以应该在前半子表中,前半子表的中间位置为:此时low=low,high=mid-1,则mid=(4+4)/2=4,4处的关键字为17,查找成功结束。以此方法,如果查找的关键字在数据集合中不存在,会出现low>high。所以结束条件为low>high或者找到关键字为止.

    a[mid]==key   return mid;//中间位置的关键字等于要查找的关键字
    a[mid]<key    low = mid + 1;//中间位置的关键字小于要查找的关键字
    a[mid]>key   high = mid - 1;//中间位置的关键字大于要查找的关键字
    

    三、实现
    方法一:非递归方法

    #include<stdio.h>
    #define N 7
    
    int Search(int a[],int low,int high,int key){
    	int mid;
    	while(low<=high){
    		mid = (low+high)/2;
    		if(a[mid]==key){//查找到
    			return mid;
    		}else if(a[mid]<key){//中间位置的关键字小于要查找的关键字
    			low = mid+1;
    		}else{//中间位置的关键字大于要查找的关键字
    			high = mid-1;
    		}
    	}
    	return -1;
    }
    
    
    int main(void)
    {
    	int a[N]={2,5,6,9,17,23,54};
    	int i,key;
    	printf("请输入你要查找的值:");
    	scanf("%d",&key);
    	i = Search(a,0,N-1,key);
    	printf("%d",i);
    	return 0;
    }
    

    递归方法

    #include<stdio.h>
    #define N 7
    
    int Search(int a[],int low,int high,int key){
    	int mid;
    	if(low>high){
    		return -1;
    	}else{
    		mid = (low+high)/2;
    		if(a[mid]==key){
    			return mid;
    		}else if(a[mid]<key){//中间位置的关键字小于要查找的关键字
    			return Search(a,mid+1,high,key);
    		}else{//中间位置的关键字大于要查找的关键字
    			return Search(a,low,mid-1,key);
    		}
    	}
    }
    
    
    int main(void)
    {
    	int a[N]={2,5,6,9,17,23,54};
    	int i,key;
    	printf("请输入你要查找的值:");
    	scanf("%d",&key);
    	i = Search(a,0,N-1,key);
    	printf("%d",i);
    	return 0;
    }
    

    二分查找会生成一棵二叉查找树
    时间复杂度o(lbn)

    展开全文
  • 编写代码在一个整形有序数组中查找具体的某个数 我们如何在一个整形数组中找到某个具体的数呢?今天跟大家分享一个二分查找算法,二分查找又称折半查找。首先,假设表中元素是按升序排列,将表中间位置记录的关键字...

    编写代码在一个整形有序数组中查找具体的某个数

    我们如何在一个整形数组中找到某个具体的数呢?今天跟大家分享一个二分查找算法,二分查找又称折半查找。首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。
    具体代码:

    int main()
    {
    	int arr[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };//定义一个整形有序数组
    	int key = 0;//我们要查找的数
    	scanf_s("%d", &key);
    	int left = 0;//数组做下标
    	int right = sizeof(arr) / sizeof(arr[0]) - 1;//数组右下标
    	while (left <= right)//当满足时,进入循环
    	{
    		int mid = (left + right) / 2;//求出中间数的下标
    		if (arr[mid] < key)//key>arr[mid],说明key在中间数右边
    		{
    			left = mid + 1;//左下标加重新得到一个子表
    		}
    		else if (arr[mid]>key)//与上面相反
    		{
    			right = mid - 1;
    		}
    		else
    		{
    			printf("找到了,下标是:%d", mid);//找到的话,打印出下标
    			break;
    		}
    	}
    	if (left>right)//
    	
    	{
    		printf("没找到");
    	}
    	return 0;
    }
    

    运行结果;
    在这里插入图片描述
    在这里插入图片描述
    二分查找的优点是比较次数少,查找速度快,平均性能好,占用系统内存较少;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。

    展开全文
  • 本文实例讲述了JavaScript使用二分查找算法在数组查找数据的方法。分享给大家供大家参考。具体分析如下: 二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入...
  • 顾名思义,折半查找就是在一个查找范围内以中间点为关键字,与给定值进行比较,从而寻找下一个查找范围。随着查找范围的不断缩小,结果越逼近给定值。 书上的定义:先确定待查记录所在的范围,然后追捕缩小范围知道...

    我们可以利用有序这个特点,设计一些高效的算法。
    例如:1.折半查找 2.斐波那契查找 3.插值查找

    1.折半查找

    实现思路

    顾名思义,折半查找就是在一个查找范围内以中间点为关键字,与给定值进行比较,从而寻找下一个查找范围。随着查找范围的不断缩小,结果越逼近给定值。

    书上的定义:先确定待查记录所在的范围,然后追捕缩小范围知道找到或者找不到该纪律为止。

    代码

    int Search_Bin(SSTable ST,int key)
    {
    //折半查找。查找num在顺序表ST中的位置
    	//只适用于有序的顺序表
    	int i,mid;
    int low=1;
    int high=ST.length-1;
    	while(low<=high)
    	{
    		mid=(high+low)/2;
    		if(ST.a[mid]==key)
    			return mid;
    		else
    			if(ST.a[mid]>key)
    				high=mid-1;
    			else
    				low=mid+1;
    	}
    	return 0;
    }
    

    性能分析

    ASL= ((n+1)/n)log2(n+1)-1,当n较大时,ASL=log2(n+1)-1
    折半查找的效率比顺序查找的高,但折半查找只适用于有序表,且限于顺序存储结构(对线性链表无法有效地进行折半查找)

    展开全文
  • 定义:二分查找也称折半查找(Binary Search),它是种效率较高的查找方法。C语言顺序存储结构可更加快捷,时间复杂度更小的查找方式。 算法要求: 1.必须采用顺序存储结构。 2.必须按关键字大小有序排列。 ...
  • 折半查找法又称为二分查找法,该方法要求带查找的表是顺序存储结构并且表中的关键字大小有序排列。 查找过程: 先确定待查记录所在的区间,然后逐渐通过待查找值与区间中间值进行比较进而调整区间大小,不断缩小范围...
  • 对于递增有序表,我们查找插入位置就是第一个关键字大于插入元素关键字的元素位置,因此折半插入就需要查找有序区一个关键字大于要插入元素关键字的元素位置。 综合以上分析 ,可以采用与直接插入排序相同的方法...
  • 1.编写函数,建立有序表,采用折半查找实现某已知的关键字的查找(采用顺序表存储结构) 2.编写函数,随机产生组关键字,利用二叉排序树的插入算法建立二叉排序树 3.编写函数,以上二叉排序树删除某指定关键字...
  • Python算法 二分查找

    千次阅读 2018-12-14 01:03:00
    二分查找(Binary Search),也被称为折半查找,是在一个有序数组中查找特定元素位置的查找算法。二分查找要求查找序列必须采用顺序存储,且表中元素按关键字有序排列。首先,假设表中元素是按升序排列,将表中间...
  • 一个90%的程序员写不对的程序,一个面试高频出现的...但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。 二分查找法充分利用了元素间的次序关系,采用分治策略,可最坏的情况下用O...
  • T1:【折半查找算法】 利用折半查找算法在一个有序表 R 插入一个关键字 为 k 的元素想,并保持表的有序性。 T2:【二叉排序树算法】 对于二叉排序树 bt,设计一个算法,输出在该树查找某个关键字 k 所经过的...
  • 2.编写一个函数,利用折半查找算法在一个有序表中插入一个元素x,并保持表的有序性。 #include<stdio.h> #define Max 50 //有序表中数据类型 typedef int KeyType; //有序表 typedef struct{ KeyType elem...
  • 折半插入排序的基本操作是在一个有序表中进行查找和插入,这个“查找”操作可利用折半查找”,由此进行的插入排序称之为折半插入排序。 从前面的有序子表中查找出待插入元素应该被插入的位置 给插入位置腾出空间...
  • 折半插入排序 C语言

    2020-11-19 17:10:14
    ①设待排序的记录存放数组Data[1…n],Data[1]是一个有序序列。 ② 循环n-1次,每次使用折半查找法,查找Data[ i ] ( i=2,…,n )已排好序的序列DataI1…i-1]的插入位置,然后将Data[ i ]插人长为i-1的有序...
  • 直接插入排序是最简单的排序方法,它采用顺序查找查找待排序记录在有序序列上的插入位置,而“查找”操作可利用折半查找”来实现,以“折半查找法”查找插入位置的排序则称为折半插入排序。...
  • 二分查找

    2019-09-25 17:21:32
    二分查找也叫折半查找,是种基本的查找算法,这种查找方法需要待查的表满足两...否则利用中间元素将表一分为二,如果中间关键字大于给定关键字,则表中进行折半查找,否则后一子表中进行折半查找。重...
  • 在一个排序了的整数数组(包含100万整数),寻找某一个特定的数。二分搜索、先构建二叉树再利用这棵树作为索引进行搜索,这两种搜索的时间复杂度都是logN。 什么时候该用第一种,什么时候该用第二种? 看到这道...
  • 搜索算法用于在一个项目集合查找一个特定的项目。搜索通常的答案是真或假,也可能是找到的某个具体值。常见的搜索算法:顺序查找、二分查找、二叉树查找、哈希查找 1.二分查找 二分查找又称折半查找,优点是比较...
  • 搜索是在一个项目集合找到一个特定项目的算法过程。搜索的几种常见方法:顺序查找、二分法查找、二叉树查找、哈希查找。 二分法查找 二分查找又称折半查找。 优点 缺点 适用对象 比较次数少,查找速度快,...
  • 排序算法之插入排序算法

    千次阅读 2008-06-15 19:37:00
     折半插入排序算法基本操作:由于直接插入排序的基本操作是在一个有序表中进行查找的和插入的,所以这个“查找”操作可以利用折半查找”来实现,这样可以减少查找的时间复杂度。时间复杂度:O(n^2)3. 2-路插入...
  • 因为插入排序的基本思想是在一个有序序列插入一个新的记录,则能够利用"折半查找"查询插入位置,由此得到的插入排序算法为"折半插入排序"。算法例如以下: void BInsertSort ()  {  // 对顺序L作折半插入...
  • 直接插入排序算法利用有序表的插入操作来实现对数据集合的排序。进行第p+1趟的插入排序时,需要前面的有序序列data[0],data[1],...,data[p]找到data[p+1]的对应的位置i,同时将data[i],data[i+1],....,data[p...
  • 排序算法比较

    2016-01-02 22:32:00
    1、折半插入排序:插入排序的基本插入是在一个有序表中进行查找和插入,这个查找可利用折半查找来实现,即为折半插入排序。2、起泡排序:首先将第一个记录的关键字和第二个记录的关键字进行比较,若为逆序,则将两个...
  • 搜索是在一个项目集合找到一个特定项目的算法过程。搜索通常的答案是真的或假的,因为该项目是否存在。 搜索的几种常见方法:顺序查找、二分法查找、二叉树查找、哈希查找 二分法查找 二分查找只能作用于有序的...

空空如也

空空如也

1 2 3
收藏数 59
精华内容 23
关键字:

利用折半查找算法在一个有序表中