青岛实习代码（2）

二分查找递归算法

 1 #include <iostream>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 #define MAXL 10000
 6 
 7 int a[MAXL],key;
 8 int BinarySearch(int low,int high)
 9 {
10      if(low>high)
11      return -1;
12 
13      int mid=(low+high)/2;
14      if(key==a[mid])
15          return mid;
16      else if(key>a[mid])
17          return BinarySearch(mid+1,high);
18      else
19          return BinarySearch(low,mid-1);
20 }
21 int main()
22 {
23     int i,N;
24     int f;
25     cin>>N;
26     for(i=0; i<N; i++)
27     cin>>a[i];
28     cin>>key;
29     f=BinarySearch(0,N-1);
30     if(f==-1)
31         cout<<"no search!"<<endl;
32     else
33         cout<<f<<endl;
34    return 0;
35 }

二分查找非递归算法

 1 #include <iostream>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 #define MAXL 10000
 6 
 7 int BinarySearch(int a[],int n,int key)
 8 {
 9    int low=0,high=n-1;
10    int mid;
11    while(low<=high)
12    {
13      mid=(low+high)/2;
14      if(key==a[mid])
15          return mid;
16      else if(key>a[mid])
17          low=mid+1;
18      else
19          high=mid-1;
20    }
21    return -1;
22 }
23 int main()
24 {
25     int a[MAXL],i,key,N;
26     int f;
27     cin>>N;
28     for(i=0; i<N; i++)
29     cin>>a[i];
30     cin>>key;
31     f=BinarySearch(a,N,key);
32     if(f==-1)
33         cout<<"no search!"<<endl;
34     else
35         cout<<f<<endl;
36    return 0;
37 }

手写快速排序

 1 #include <iostream>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 #define MAXL 10000
 6 
 7 int a[MAXL],n;
 8 void QuickSort(int low,int high)
 9 {
10     if(low<high)
11     {
12         int x,l,h;
13         l=low,h=high;
14         x=a[low];
15         while(low<high)
16         {
17             while(low<high&&a[high]>=x)  --high;
18             a[low]=a[high];
19             while(low<high&&a[low]<=x) ++low;
20             a[high]=a[low];
21         }
22         a[low]=x;
23         QuickSort(l,low-1);
24         QuickSort(low+1,h);
25     }
26 }
27 
28 void show()
29 {
30     int i;
31     for(i=0; i<n; i++)
32         cout<<a[i]<<" ";
33     cout<<endl;
34 }
35 int main()
36 {
37     int i;
38     cin>>n;
39     for(i=0; i<n; i++)
40         cin>>a[i];
41     QuickSort(0,n-1);
42     show();
43     return 0;
44 }