BJFU_数据结构习题_298基于快排思想的查找

我会带着你远行 2023-06-19 06:46 10阅读 0赞

欢迎登录北京林业大学OJ系统  
[http://www.bjfuacm.com][http_www.bjfuacm.com]

### 298基于快排思想的查找 ###

**描述**  
借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于key的记录。设此组记录存放于数组r\[l…n\]中。若查找成功，则输出该记录在r数组中的位置及其值，否则显示“not find”信息。  
**输入**  
多组数据，每组数据三行。第一行为序列的长度n，第二行为序列的n个元素（元素之间用空格分隔，元素都为正整数），第三行为要查找的key值。当n等于0时，输入结束。  
**输出**  
每组数据输出一行。如果查找成功，输出key在数组中的位置（1到n）和key的值，两个数字之间用空格隔开。如果查找失败，输出“not find”。  
**输入样例 1**  
5  
1 2 43 5 6  
43  
4  
1 9 20 3  
21  
7  
20 30 40 10 1 2 3  
0  
**输出样例 1**  
3 43  
not find  
4 10

#include<iostream>
    using namespace std;
    int Search(int r[],int low,int high,int key)
    {
        
        while(low<high)
        {
        
            if(r[low]>key&&r[high]<key)
            {
        
                high--;
    			low++;
            }
    		while(low<=high&&r[high]>key)
    			high--;
    		if(r[high]==key)
    			return high;
    		while(low<=high&&r[low]<key)
    			low++;
    		if(r[low]==key)
    			return low;
    	}
        cout<<"not find"<<endl;
    	return 0;
    }
    int main()
    {
        
        int n;
        while(cin>>n&&n!=0)
        {
        
            int r[100],key;
            for(int i=0;i<n;i++)
                cin>>r[i];
            cin>>key;
            if(Search(r,0,n,key))
    			cout<<Search(r,0,n,key)+1<<" "<<key<<endl;
        }
    }

[http_www.bjfuacm.com]: http://www.bjfuacm.com