描述
借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于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
10
0
样例输出1
3 43
not find
4 101
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47#include<iostream>
using namespace std;
int search(int r[],int low,int high,int key)
{
while(low<high)
{
while(r[low]>key&&r[high]<key)
{
high--;
low++;
}
while(low<=high&&r[high]>key) high--;
if(r[high]==key)
return high+1;
while(low<=high&&r[low]<key) low++;
if(r[low]==key) return low+1;
}
return 0;
}
int main()
{
int a[100];
while(1)
{
int n;
cin>>n;
if(n==0)
break;
else
{
for(int i=0;i<n;i++)
{
cin>>a[i];
}
int key;
cin>>key;
int flag=search(a,0,n-1,key);
if(flag==0)
cout<<"not find"<<endl;
else
{
cout<<flag<<" "<<key<<endl;
}
}
}
return 0;
}
