精华内容
下载资源
问答
  • C++实现有序表折半查找

    千次阅读 2015-05-12 10:10:26
    折半查找(Binary Search)的查找过程是:先确定等查记录所在范围(区间),然后逐步缩小范围直到找到或找不到该记录为止。 2>算法 3>算法实现 #include using namespace std; #define ARRAY_SIZE 11 /* ...

    1>算法思想:

    折半查找(Binary Search)的查找过程是:先确定等查记录所在范围(区间),然后逐步缩小范围直到找到或找不到该记录为止。

    2>算法

    3>算法实现

    #include<iostream>
    using namespace std;
    
    #define ARRAY_SIZE 11
    /*
    description:
    在标准输出设备上显示数组元素。
    parameter:
    int* p:指向整形数组首元素的指针
    int length:整形数据长度
    */
    void myshow(int*  p_start,int length){
    	for(int i=0;i<length;i++){
    		cout<<"["<<i<<"]:"<<*(p_start+i)<<endl;
    	}
    	cout<<endl;
    }
    /*
    返回与关键字key相等的数据元素下标,若不存在,返回-1
    @param 
    int *p_start:首元素地址
    int length:列表长度
    int key :要查找的关键字
    */
    int searchBin(int *p_start ,int length,int key){
    	int low=0;
    	int high=length-1;
    	int mid=-1;
    	while(low <=high){
    		mid=(low+high)/2;
    		if(p_start[mid]==key){
    			return mid;//查找成功
    		}else if(p_start[mid]>key){//待查记录在低半区间
    			high=mid-1;
    		}else{//p_start[mid]<key ,待查记录在高半区间
    			low=mid+1;
    		}
    	}
    	return -1;//查找不成功
    	
    }
    int main(){
    
    	int list[ARRAY_SIZE]={5,13,19,21,37,56,64,75,80,88,92};
    	cout<<"待查找序列:"<<endl;
    	myshow(list,ARRAY_SIZE);
    
    	int index=-1;
    	for(int i=0;i<ARRAY_SIZE;i++){
    		index =searchBin(list,ARRAY_SIZE,list[i]);
    		cout<<"查找"<<list[i]<<"返回下标为:"<<index<<endl;
    	}
    	index =searchBin(list,ARRAY_SIZE,100);
    	cout<<"查找"<<100<<"返回下标为:"<<index<<endl;
    
    
    	return 0;
    
    }
    

    运行结果:

    4>时间及空间复杂度


    展开全文
  • 有序表折半查找的递归算法

    千次阅读 2017-11-16 20:33:55
    #include #include typedef struct{ int key; }Elemtype; typedef struct{ Elemtype *elem; int length; }Table; int Create(Table &S,int n){ S.elem=(Elemtype *)malloc(n*sizeof(Elemtype));...S.elem){

    欢迎加qq群:453398542 学习讨论,会定期分享资料课程,解答问题。

    #include<stdio.h>
    #include<stdlib.h>
    typedef struct{
    	int key;
    }Elemtype;
    typedef struct{
    	Elemtype *elem;
    	int length;
    }Table;
    int Create(Table &S,int n){
    	S.elem=(Elemtype *)malloc(n*sizeof(Elemtype));
    	if(!S.elem){
    		S.length=0;
    		exit(0);	
    	}
    	else
    		S.length=n;
    		return 1;
    }
    int Search(Table S,int key,int low,int high){
    	int mid;
    	while(low<=high){
    		mid=(low+high)/2;
    		if(key=S.elem[mid].key){
    			return mid;
    		}
    		else if(key<S.elem[mid].key){
    			return Search(S,key,low,mid-1);
    		}
    		else 
    			return Search(S,key,mid+1,high);
    	}
    	return 0;//查找失败 
    }
    int main(){
    	int key,i,n;
    	Table S;
    	printf("输入表长:");
    	scanf("%d",&n);
    	Create(S,n);
    	printf("输入有序表:");
    	for(i=0;i<S.length;i++){
    		scanf("%d",&S.elem[i].key);
    	}
    	printf("输入要查找的数:");
    	scanf("%d",&key);
    	printf("元素所在位置:%d",Search(S,key,0,n-1)+1);
    	return 0;
    }

     

    展开全文
  • int Search_BIn(SSTable ST,KeyType key) { int low=1,high=ST.length; int mid; while(low<=high) { mid=(low+high)/2;...if(EQ(key,ST.elem[mid].key))return mid;...else if(LT(key,ST.elem[mid].key))high=mid-1;...

    int Search_BIn(SSTable ST,KeyType key)
    {
    int low=1,high=ST.length;
    int mid;
    while(low<=high)
    {
    mid=(low+high)/2;
    if(EQ(key,ST.elem[mid].key))return mid;
    else if(LT(key,ST.elem[mid].key))high=mid-1;
    else low=mid+1;
    }
    return 0;
    }

    展开全文
  • 静态查找表。实现有序表折半查找算法 静态查找表。实现有序表折半查找算法 静态查找表。实现有序表折半查找算法静态查找表。实现有序表折半查找算法
  • 有序表的查找——折半查找分析

    千次阅读 2020-06-03 21:31:59
    二分查找要求:线性表是有序表,即表中结点按关键字有序,并且要用数组向量作为表的存储结构,不能使用链表,不妨设有序表是递增有序的。 2、二分查找的基本思想 二分查找的基本思想是:(设R[low…high]是当前的...

    一、折半查找的查找过程

    1、折半查找(Binary Search)

    折半查找又称二分查找,它是一种效率较高的查找方法。

    二分查找要求:线性表是有序表,即表中结点按关键字有序,并且要用数组向量作为表的存储结构,不能使用链表,不妨设有序表是递增有序的。

    2、二分查找的基本思想

    二分查找的基本思想是:(设R[low…high]是当前的查找区间)

    (1)首先确定该区间的中点位置:R[mid]

    (2)然后将待查的K值与R[mid].key比较:若相等,则查找成功并返回此位置,否则须确定新的查找区间,继续二分查找,具体方法如下:

    ①若R[mid].key>K,则由表的有序性可知R[mid…n].keys均大于K,因此若表中存在关键字等于K的结点,则该结点必定是在位置mid左边的子表R[1…mid-1]中,故新的查找区间是左子表R[1…mid-1]。

    ②类似地,若R[mid].key<K,则要查找的K必在mid的右子表R[mid+1…n]中,即新的查找区间是右子表R[mid+1…n]。下一次查找是针对新的查找区间进行的。

    因此,从初始的查找区间R[1…n]开始,每经过一次与当前查找区间的中点位置上的结点关键字的比较,就可确定查找是否成功,不成功则当前的查找区间就缩小一半。这一过程重复直至找到关键字为K的结点,或者直至当前的查找区间为空(即查找失败)时为止。
    在这里插入图片描述
    在这里插入图片描述

    二、折半查找的实现

    
    int Search_Bin(StaicTable ST, Elemtype x,int low, int high){
    //本函数在递增表ST中进行折半查找,如果查找成功,返回该元素所在位置,否则返回0
       found=false;
       while (low≤high  && !found) 
          {  mid=(low+high) / 2;
             if (x>ST[mid].key)     low=mid+1;
             else if (x<ST[mid].key)  high=mid-1;
             else                   found=true;
          } 
          if (found )  return mid;
          else           
             return 0;
     }
    

    三、折半查找的性能分析

    在这里我们先假定要查找的元素数目n恰好构成一棵满二叉树,然后为它加上n+1个外部结点,表示查找不成功的情形。

    折半查找的过程可以用下面这样的判定树来模拟:
    在这里插入图片描述
    该树有m(=2n+1)个结点,高度为 K= log(m+1)=log(n+1)+1。

    最坏情形下,就是查找不成功的情形必须要查到叶子结点,查找次数为K次,即log(n+1)+1

    要求折半查找的平均情形,我们设落在每个结点的概率均为 1/m, 则总的查找次数为:

    11/m + 2(21/m) + 3(41/m) + …… + k(2k-1*1/m)
    在这里插入图片描述
    而m=2k-1,故A(n)=((k-1)2k+1)/(2k)=(k-1)+1/2k

    一般化(即非满二叉树),有:
    在这里插入图片描述

    四、总结

    虽然二分查找的效率高,但是要将表按关键字排序。而排序本身是一种很费时的运算。既使采用高效率的排序方法也要花费O(nlog2n)的时间。

    二分查找只适用顺序存储结构。为保持表的有序性,在顺序结构里插入和删除都必须移动大量的结点。因此,二分查找特别适用于那种一经建立就很少改动、而又经常需要查找的线性表。

    对那些查找少而又经常需要改动的线性表,可采用链表作存储结构,进行顺序查找。链表上无法实现二分查找。

    展开全文
  • 有序表折半查找

    千次阅读 2018-07-07 01:40:09
    有序表折半查找 #include &lt;iostream&gt; using namespace std; typedef struct { int r[100]; int length; }table; int create(table &amp;t) { int a; t.length=0; cin&gt;&gt;a;...
  • Java有序表查找:折半查找、二分查找、差值查找和斐波那契查找  【尊重原创,转载请注明出处】http://write.blog.csdn.net/postedit?ticket=ST-84189-RPiSkdLK6Dt1Oyqsgvsx-passport.csdn.net  目前查找方法...
  • 主要介绍了PHP有序表查找之二分查找(折半查找)算法,简单介绍了二分查找法的概念、原理并结合实例形式分析了php基于二分查找算法进行有序线性表查找的相关操作技巧,需要的朋友可以参考下
  • 有序表的查找-折半查找

    千次阅读 2019-04-11 16:46:12
    low,high 分别为待查找范围的上界和下界,指针mid指示区域的中间位置,折半查找的范围其实就是用mid不断更新low或者high的位置,直到找到目标值,注意查找之前需要确保有序的 mid=(low+high)/2 设目标值为...
  • 折半查找的基本思想是:在有序表中,取中间记录作为比较对象,若给定值与中间记录的关键字相等,则查找成功;若给定值小于中间记录的关键字,则在中间记录的左半区继续查找;若给定值大于中间记录的关键字,则在中间...
  • 有序表——折半查找

    千次阅读 2017-11-12 18:44:25
    二分查找又称折半查找,前提要求数据序列呈现线性结构,即必须是经过排序的。 基本思路:  在一组有序序列中,取中间值与给定关键字进行比较,如果给定关键字大于该值关键字,则要查找的关键字位于有序序列的后半...
  • 有序表的查找(折半查找

    千次阅读 2015-12-28 13:09:10
     对有序表可以采用折半查找(binary search),又称二分查找。  设有序数组r中每个记录的关键字值按升序排列为:  r0.key, r1.key, r2.key, …, rm.key, …, rn-1.key  其中,n为记录个数。当i时,有ri....
  • 有序表查找——折半查找

    千次阅读 2017-05-08 11:01:03
    折半查找也称(二分查找) 前提:线性表中的记录必须是关键码有序(通常从小到大),线性表必须采用顺序存储。 思想:取中间记录作为比较对象 , 若给定值与中间记录的关键字相等,则成功;若小于,则在中间记录...
  • 有序序列折半查找构建判定树

    万次阅读 多人点赞 2016-10-25 16:07:13
    需要特别强调的是折半查找的判定树是一棵平衡树。一般对于一个有序序列折半查找过程,需要从中间结点...举例如下:构建一个12个元素的有序表的判定树。不妨假设是1,2,3,4,… , 12 则mid=(1+12)÷2=6mid = (1+12
  • 有序表查找(折半查找与插值查找) #include "stdafx.h" #include &lt;iostream&gt; #include &lt;string&gt; using namespace std; //折半查找的时间复杂度为O(logn) 但对于需要频繁...
  • 概要引入折半查找基本概念折半查找java代码实现折半查找算法复杂度分析折半查找改进版1:插值查找折半查找改进版2:斐波那契查找总结 引入 顺序查找虽然算法非常简单,对静态查找的记录没有任何要求,但是当查找...
  • 有序表查找---折半查找算法

    万次阅读 2019-03-10 20:00:31
    折半查找的基本思想是:在有序表中,取中间值为比较对象,如果给定的值和中间值的关键字相等,则查找成功;若给定值小于中间记录的关键字,则在中间记录的左半区继续查找;若给定的值大于中间值的关键字,则在中间...
  • 二分查找法(binary search)也称为折半查找法,用来查找一组有序的记录数组中的某一记录,其基本思想是:将记录按有序化(递增或递减)排列,在查找过程中如果要找的元素值小于该中点元素,则将待查序列缩小为左半...
  • 折半查找,又为二分法前提:线性表中的记录为有序的(一般是从小到大)基本思想:在有序表中,取中间值和要查找的值比较 若等于中间值,则中间值即为要查找的 若小于中间值,则中间值的左半区域继续查找 若...
  • 有序表折半查找

    千次阅读 2010-12-01 17:26:00
    有序表折半查找 有序表即使表中数据元素按照关键码升序或者降序排序。 折半查找的主要思想: 在有序表中,取中间元素作为比较对象,若给定值与中间元素的关键码相等则查找成功;若给定值小于...
  • 折半查找的关键点有两个: 1.有序表 2.两个索引low,high。 low = 0; high = size; 因为是有序表,low 和 high的中间值,也就是low 和high的平均值mid = (high + low) / 2. 比较Key值与索引mid的处的值: ...
  • //请写出对有序表进行折半查找的非递归算法,并将对应的程序调试运行通过 #include #include #define N 100 typedef int Status; typedef int ElemType;typedef struct {//创建有序表 ElemType *list; int length;...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 16,972
精华内容 6,788
关键字:

有序表的折半查找