折半查找方法详解

591 阅读 0 评论 0 点赞

输入格式：
第一行输入一个整数n，表示有序表的元素个数，接下来一行n个数字，依次为表内元素值。 然后输入一个要查找的值。

输出格式：
输出这个值在表内的位置，如果没有找到，输出"NOT FOUND"。

输入样例：
5
1 3 5 7 9
7
输出样例：
4
输入样例：
5
1 3 5 7 9
10
输出样例：
NOT FOUND
    
    #include <iostream>
    using namespace std;
     
    #define MAXSIZE 50
    typedef int KeyType;
     
    typedef  struct                     
    { KeyType  key;                                             
    } ElemType;  
     
    typedef  struct
    { ElemType  *R; 
      int  length;
    } SSTable;                      
     
    void  Create(SSTable &T)
    { int i;
      T.R=new ElemType[MAXSIZE+1];
      cin>>T.length;
      for(i=1;i<=T.length;i++)
         cin>>T.R[i].key;   
    }
    //
    //方法1, 
     
    int  Search_Bin(SSTable T, KeyType k)
    {
    	int max=T.length;
       int min=0;
        bool flag=false;
        int count=(max-min)/2+1;//指的是mid
        while(count)
        {
            
        	if(T.R[count+min].key==k)
        	{ flag=true;
        		break;
    		}
    		else if(T.R[count+min].key<k)
    		{
    		   min=count;
    		   //
    		    //cout<<min+count<<endl;
    		   
    		   count/=2;
    		   
    		  
    		}
    		else{
    			max=count;
    			//
    			
    			count=(max-min)/2;
    			//
    			
    		}
        	
    	}
    if(flag)
    	{
    		return count;
    	}	
    	else{
    		return 0;
    		}
    	
    } 
     
    //方法2
    int  Search_Bin(SSTable T, KeyType k)
    {
    	int left=1;
    	int right=T.length;
    	int mid=1;
    	bool flag=false;
    	while(left<right)
    	{
    		mid=(left+right)/2;
    		if(T.R[mid].key==k)
    		{
    			flag=true;
    			break;
    		}
    		if(T.R[mid].key>k)
    		{
    			right=mid-1;
    		}
    		else{
    			left=mid+1;
    		}
    	 } 
        if(flag)
    	{
    		return mid;
    	}	
    	else{
    		return 0;
    		}
    }  
     
     
     
    //
    int main () 
    {  SSTable T;  KeyType k;
       Create(T);
       cin>>k;
     
      int pos= Search_Bin(T,k);
      if(pos==0) cout<<"NOT FOUND"<<endl;
     else cout<<pos<<endl;
      return 0;
    }
     
     
     
    //两种方法都能ac,都是二分的思想，推荐用第二种，好想和理解，第一种是自己纯想的，第二种是受一篇文章的启发写的
    
	给一个严格递增数列，函数int Search_Bin(SSTable T, KeyType k)用来二分地查找k在数列中的位置。

函数接口定义：
```cpp
    int  Search_Bin(SSTable T, KeyType k)
```
其中T是有序表，k是查找的值。

裁判测试程序样例：
 
    #include <iostream>
    using namespace std;
     
    #define MAXSIZE 50
    typedef int KeyType;
     
    typedef  struct                     
    { KeyType  key;                                             
    } ElemType;  
     
    typedef  struct
    { ElemType  *R; 
      int  length;
    } SSTable;                      
     
    void  Create(SSTable &T)
    { int i;
      T.R=new ElemType[MAXSIZE+1];
      cin>>T.length;
      for(i=1;i<=T.length;i++)
         cin>>T.R[i].key;   
    }
     
    int  Search_Bin(SSTable T, KeyType k);
     
    int main () 
    {  SSTable T;  KeyType k;
       Create(T);
       cin>>k;
       int pos=Search_Bin(T,k);
       if(pos==0) cout<<"NOT FOUND"<<endl;
       else cout<<pos<<endl;
       return 0;
    }
     
    /* 请在这里填写答案 */

0.0分

0 人评分

本文分类：文章列表
浏览次数：591 次浏览
发布日期：2019-10-07 11:00:30
本文链接：https://blog.dotcpp.com/a/62003

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

折半查找方法详解

评论列表共有 0 条评论

发表评论取消回复

折半查找方法详解

一笔画问题（dfs）

C++ ： 类和两种访问权限的练习

C++ ： 类和两种访问权限的练习

幸运儿（约瑟夫环-模拟+ Vector）

评论列表 共有 0 条评论

发表评论 取消回复

C++ ：类和两种访问权限的练习

C++ ：类和两种访问权限的练习

评论列表共有 0 条评论

发表评论取消回复