#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;
}