二分查找
Coddy C++ 数组 课程的第 10 课，共 26 课。
在数组中进行 O(n) 时间的查找已经不错了，但使用一种叫作 Binary search 的方法，还可以进一步优化到 O(log n)。
使用 Binary Search 的条件：数组中的元素必须按升序或降序排列。
例如，
int Arr[]={1,2,3,4,5};
int Brr[]={5,3,9,6,7};在 Arr 中，由于所有元素都按升序排列，我们可以使用 Binary search 查找元素。
在 Brr 中，我们不能使用 Binary Search，因为 Brr 中的元素排列是随机的。
基本逻辑
检查数组正中间的元素，
- 如果它与目标元素相等，就输出它；
- 如果它小于目标元素，就在剩余数组的右侧查找；
- 如果它大于目标元素，就在剩余数组的左侧查找。
重复这个过程，直到找到你要查找的目标元素；如果找不到，就返回 -1。
详细过程
1. 首先，初始化 2 个变量，分别指向数组的起始位置和结束位置。然后使用 while 循环，并设置条件：起始位置始终小于或等于结束位置。
int s=0; //起始位置
int e=n; //结束位置
while(s<=e){
}2. 通过计算 (s+e)/2 找到中间位置。如果 mid 恰好等于目标元素，就返回它。
int s=0; //起始位置
int e=n; //结束位置
while(s<=e){
int mid=(s+e)/2; //数组的中间位置
if(arr[mid]==key){ //如果相等，就返回它
return mid;
}
}3. 如果中间元素大于目标元素，就说明目标元素一定在数组的左侧。因此，我们将数组的结束位置移到 mid-1。现在，数组大小只有 n/2，我们可以重复这个过程。
int s=0; //起始位置
int e=n; //结束位置
while(s<=e){
int mid=(s+e)/2; //数组的中间位置
if(arr[mid]==key){
return mid;
}
else if(arr[mid]>key){
e=mid-1; //将结束位置移到 mid-1
}
}4. 如果以上条件都不成立，就说明目标元素大于中间元素。因此，我们在数组的右侧查找，并将数组的起始位置移到 mid+1。
int s=0;
int e=n;
while(s<=e){
int mid=(s+e)/2;
if(arr[mid]==key){
return mid;
}
else if(arr[mid]>key){
e=mid-1;
}
else{
s=mid+1; //将起始位置移到 mid+1
}
}一直运行程序，直到找到目标元素。如果数组中没有这个元素，就返回 -1。
时间复杂度
每一步中，元素数量都会减半。这意味着每一步的执行时间都是上一步的一半，也就是说，所需时间会按对数级缩短。因此，二分查找的时间复杂度为 O(log n)。
挑战
简单给定一个数组、它的大小和一个整数 k，完成函数 BinarySearch。
如果键元素存在，返回它所在位置的索引；如果不存在，返回 -1。
亲手试试
#include<vector>
#include<iostream>
using namespace std;
int BinarySearch(vector<int>arr, int n, int key){
}
C++ 数组中的所有课
自己练习： C++ 在线编译器