毛豆

用户名：liuyt

访问量：16842

签　名：

等　　级
排　　名	1025
经　　验	3310
参赛次数	3
文章发表	34
年　　龄	22
在职情况	学生
学　　校	燕山大学
专　　业	计算机

　　自我简介：

TA的其他文章

bfs与dfs实战解题
浏览：665

背包九讲第一篇
浏览：602

ysu情报问题解析
浏览：342

你可能喜欢

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

【求帮助】C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

折半查找方法详解

　　作者: 毛豆　　　　发表时间：2019-10-07 11:00:30 浏览：383　|　评论：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 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

毛豆

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

【求帮助】C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C++代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

折半查找方法详解

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

简单的a+b （C语言代码）

最小公倍数（C语言代码）

printf基础练习2 （C语言代码）

用筛法求之N内的素数。（C++代码）

C语言程序设计教程（第三版）课后习题9.1 （C语言代码）

K-进制数（C语言描述，蓝桥杯）

矩形面积交（C++代码）

字符串输入输出函数（C语言代码）

简单的a+b （C语言代码）

毛豆

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

【求帮助】C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C++代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

折半查找方法详解

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

简单的a+b （C语言代码）

最小公倍数 （C语言代码）

printf基础练习2 （C语言代码）

用筛法求之N内的素数。 （C++代码）

C语言程序设计教程（第三版）课后习题9.1 （C语言代码）

K-进制数 （C语言描述，蓝桥杯）

矩形面积交 （C++代码）

字符串输入输出函数 （C语言代码）

简单的a+b （C语言代码）

　　评论区

最小公倍数（C语言代码）

用筛法求之N内的素数。（C++代码）

K-进制数（C语言描述，蓝桥杯）

矩形面积交（C++代码）

字符串输入输出函数（C语言代码）