理论：

$二分查找$又称为$折半查找$，顾名思义，指的是$每次的查找范围折半$

它的优点是：比较次数少、查找速度快、平均性能好

但它也有缺点：要求待查找的数据已被整理为有序，换而言之，就是要求数组有序

基本原理：

1.先确认有序序列的中位数

2.如果中位数>要找的元素，那么要找的元素就会在中位数的左边，否则就在右边

---

代码：

#include <bits/stdc++.h>
using namespace std;

int n, arr[100 + 1], value;
int binarySearch(int arr[], int low, int high, int value){ //从左往右的变量意义依次为:数组,左指针,右指针,要查找的数据 
	if (low > high) return -1; //如果左指针超过了右指针,那么返回-1以表示没找到
	int mid = low + ((high - low) / 2); //中间指针
	if (arr[mid] == value) return mid; //如果找到了value,就返回下标(mid)
	else if (arr[mid] > value){ //如果value在mid的左边 
		binarySearch(arr, low, mid - 1, value); //那就在mid的左边寻找; 
	} else if (arr[mid] < value){ //如果value在mid的右边 
		binarySearch(arr, mid + 1, high, value); //那就在mid的右边寻找; 
	} 
}
int main(){
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> arr[i];
	cin >> value;
	sort(arr + 1, arr + 1 + n);
	int ans = binarySearch(arr, 1, n, value);
	if (ans == -1) cout << "没有找到" << endl;
	else cout << "找到了" << endl;
	return 0;
}

非递归代码：

int BinarySearch2(int arr[], int len, int target) {
	int low = 0;
	int high = len;
	int mid = 0;
	while (low <= high) {
		mid = (low + high) / 2;
		if (target < arr[mid]) high = mid - 1;
		else if (target > arr[mid]) low = mid + 1;
		else return mid;
	}
	return -1;
}

输入输出样例：

样例1：

输入

10
2 6 7 1 3 0 9 5 4 8
6

输出

找到了

样例2：

输入

10
14 12 56 33 89 77 98 63 23 10
114514

输出

没有找到