一般法:
#include<stdio.h>
#define MAX_N 100
int binary_search(int *arr, int n, int x) {
int head = 0, tail = n - 1, mid;
while (head <= tail) {
mid = (head + tail) >> 1;
if (arr[mid] == x) return mid;
if (arr[mid] < x) head = mid + 1;
else tail = mid - 1;
}
return -1;
}
int main(){
int arr[MAX_N + 5] = {0};
int n;
int x;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
while (~scanf("%d", &x)) {
printf("%d\n", binary_search(arr, n ,x));
}
return 0;
}
递归法:
#include<stdio.h>
#define MAX_N 100
int binary_search(int *arr, int head, int tail, int x) {
int mid = (head + tail) >> 1;
if (head > tail) return -1;
if (arr[mid] == x) return mid;
if (arr[mid] < x){
head = mid + 1;
}
else {
tail = mid - 1;
}
return binary_search(arr, head, tail, x);
}
int main(){
int arr[MAX_N + 5] = {0};
int n;
int x;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
while (~scanf("%d", &x)) {
printf("%d\n", binary_search(arr,0, n - 1 ,x));
}
return 0;
}