c++折半查找的次数

题目描述

给你一个无重复数的有序序列，如果采用折半查找的方式，对于给定的数，需要比较几次找到，请编程实现。

输入

第一行是N，表示序列中数的个数，序列最长1000，第二行是一个有序序列，第三行是要找的数x。

输出

如果找到x，输出折半比较的次数，否则输出NO。

样例输入

11
5 13 19 21 37 56 64 75 80 88 92
19

样例输出

2

示例代码

#include
using namespace std;
int a[1001];

int f(int* a, int s, int e, int c, int x) {
	if (a[(e + s) / 2] == x && (e - s) != 1) {
		return c;
	}
	if ((e - s) == 1 && a[(e + s) / 2] == x || a[(e + s) / 2 + 1] == x ) {
		return c;
	}
	if (s >= e) {
		return 0;
	}
	if (a[(e + s) / 2] > x) {
		f(a, s, (e + s) / 2 - 1, c + 1, x);
	}
	else if (a[(e + s) / 2] < x) {
		f(a, (e + s) / 2 + 1, e, c + 1, x);
	}
}

int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	int x;
	cin >> x;
	int cnt = f(a, 1, n, 1, x);
	if (cnt == 0) {
		cout << "NO";
	}
	else {
		cout << cnt;
	}
	return 0;
}