You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
76 lines
1.2 KiB
76 lines
1.2 KiB
#include<bits/stdc++.h>
|
|
using namespace std;
|
|
#define MAX 101
|
|
void input(int num[]) {
|
|
int i;
|
|
|
|
srand((unsigned)time(NULL));
|
|
for(i=1; i<MAX; i++)
|
|
num[i]=rand()%100;
|
|
}
|
|
void output(int num[]) {
|
|
int i;
|
|
|
|
for(i=1; i<MAX; i++) {
|
|
printf("%5d", num[i]);
|
|
if(0==i%10)
|
|
printf("\n");
|
|
}
|
|
}
|
|
void sort(int num[], int low, int high) { /* quick sort */
|
|
int l, h;
|
|
|
|
if(low<high) {
|
|
l=low;
|
|
h=high;
|
|
num[0]=num[l]; /* save pivot */
|
|
|
|
while(l<h) {
|
|
while(l<h && num[h]>=num[0]) h--;
|
|
num[l]=num[h];
|
|
while(l<h && num[l]<=num[0]) l++;
|
|
num[h]=num[l];
|
|
}
|
|
num[l]=num[0]; /* insert pivot */
|
|
|
|
sort(num, low, l-1);
|
|
sort(num, l+1, high);
|
|
}
|
|
}
|
|
int find(int num[], int x, int low, int high) {
|
|
int mid;
|
|
|
|
while(low<=high) {
|
|
mid=(low+high)/2; /* find is OK */
|
|
|
|
if(x==num[mid])
|
|
return mid;
|
|
else if(x<num[mid])
|
|
high=mid-1;
|
|
else
|
|
low=mid+1;
|
|
}
|
|
return 0;
|
|
}
|
|
int main() {
|
|
int x, pos, num[MAX];
|
|
input(num);
|
|
|
|
printf("sort before... \n");
|
|
output(num);
|
|
sort(num, 1, MAX-1);
|
|
printf("sort after... \n");
|
|
output(num);
|
|
|
|
printf("Enter find num: ");
|
|
scanf("%d", &x);
|
|
pos=find(num, x, 1, MAX-1);
|
|
if(pos)
|
|
printf("OK! %d is found in pos: %d\n", x, pos);
|
|
else
|
|
printf("Sorry! %d is not found... in num\n", x);
|
|
return 0;
|
|
}
|
|
|
|
|