>>761
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX 100000
int compare(const void*, const void*);
int binary_search(int*, int, int, int);
int main(void) {
static int a[MAX]; int i, n;
srand( (unsigned int)time(NULL) );
for (i=0 ;i < MAX; i++) { a[i] = rand(); }
qsort((void*)a, (size_t)MAX, sizeof(int), compare);
printf("Input:"); scanf("%d", &n);
if ( binary_search(a, n, 0, MAX-1) == -1) printf("not found\n");
}
int compare(const void* left, const void* right) {
return (*(int*)left == *(int*)right)? 0 : (*(int*)left < *(int*)right)? -1 : 1;
}
int binary_search(int* a, int k, int l, int r) {
static int ct=1;
if (a[l] == k) { printf("%d OK\n", ct); return l; }
if ( (a[l] < k)&&(k <= a[(l+r)/2]) ) { printf("%d NG\n", ct++); return binary_search(a, k, l, (l+r)/2); }
if ( (a[(l+r)/2] < k)&&(k <= a[r]) ) { printf("%d NG\n", ct++); return binary_search(a, k, (l+r)/2+1, r); }
return -1;
}