简介
看b站左神视频的学习笔记，按照他提出的几个针对二分法查找的问题，自己写了下C++的代码，可能有错，欢迎各位指出。
问题1
基本的二分查找，原理不赘述，可以去看
原视频
。
代码实现
int BinSearch(const vector<int>& arr, const int& dest)
{
// 初始化两个Index
int lowIndex = 0;
int highIndex = arr.size() - 1;
int midIndex = (lowIndex + highIndex) / 2;
while (lowIndex <= highIndex)
{
if (arr[midIndex] == dest)
{
// 说明找到目标值了，直接返回对应Index值即可
return midIndex;
}
else if (arr[midIndex] < dest)
{
// 说明目标值可能在(midIndex, highIndex]间，则更新lowIndex
lowIndex = midIndex + 1;
}
else
{
// 说明目标值可能在[lowIndex, midIndex)间，则更新highIndex
highIndex = midIndex - 1;
}
midIndex = (lowIndex + highIndex) / 2;
}
// 函数如果没有在循环中返回，则必然是没有找到结果，则返回-1
return -1;
}
void main()
{
vector<int> arr{ 11,12,13,34,40,45,46,67,79,80,84,100 };
int dest = 34;
int index = BinSearch(arr, dest);
if (index != -1)
{
cout << "对应位置为：" << index << ", 对应元素为：" << arr[index] << endl;
}
else
{
cout << "未找到对应元素！" << endl;
}
system("pause");
}
问题2
问题概述
要求用二分法找到一个有序数组中（升序）第一次大于等于某个数字的位置
。
比如说有一个数组arr = {1, 4, 6, 7, 7, 7, 9}，要求找出第一个大于等于6的位置，那么此时返回对应数值为第一次数值6的Index，即返回2。
算法思路
和普通二分法查找的区别在于，这种问题一定要不停地二分直到区间下边界大于区间上边界，而不会因为数值满足条件而中断循环，相当于要遍历整个可能满足条件的部分有序数组，并用一个额外的变量minIndex来记录当前满足条件的最小数组下标。
就按上面的例子来说，现在要在数组里面找出第一个大于等于6对应元素的位置，那么查找步骤为：
步骤1：
lowIndex = 0，highIndex = 6，midIndex = 3，arr[midIndex] = 7 > 6，对于一般的二分法，到这里已经数值满足条件，可以返回，但是此时要求找到第一个满足数值条件的位置，所以要继续二分，并记录minIndex = midIndex = 3；
步骤2：
lowIndex = 0，highIndex = midIndex – 1 = 2，midIndex = 1，arr[midIndex] = 4 < 6，不满足条件，故不修改minIndex的值，继续二分，此时minIndex = 3；
步骤3：
lowIndex = midIndex + 1 = 2，highIndex = 2，midIndex = 2，arr[midIndex] = 6 = 6，满足条件，修改minIndex的值，继续二分，此时minIndex = 2；
步骤4：
lowIndex = 2，highIndex = 2 – 1 = 1，不满足循环条件 lowIndex <= highIndex，则算法结束；
代码实现
int BinSearch_ForFirstBiggerValue(const vector<int>& arr, const int& dest)
{
// 将minIndex初始化为-1，若后续没有对这个数值进行修改，说明没有满足条件的数值，则函数也返回-1
int minIndex = -1;
// 初始化3个Index
int lowIndex = 0;
int highIndex = arr.size() - 1;
int midIndex = (lowIndex + highIndex) / 2;
while (lowIndex <= highIndex)
{
if (arr[midIndex] >= dest)
{
// 满足条件，则记录下当前的Index，并继续向前二分
minIndex = midIndex;
highIndex = midIndex - 1;
}
else
{
// 当前值比目标值小了，说明满足条件的值在以midIndex划分的后半部分，则向后二分
lowIndex = midIndex + 1;
}
midIndex = (lowIndex + highIndex) / 2;
}
return minIndex;
}
void main()
{
vector<int> arr{ 11,12,13,34,40,45,46,67,79,80,84,100 };
int dest = 37;
int index = BinSearch_ForFirstBiggerValue(arr, dest);
if (index != -1)
{
cout << "对应位置为：" << index << ", 对应元素为：" << arr[index] << endl;
}
else
{
cout << "未找到对应元素！" << endl;
}
system("pause");
}
问题3
问题描述
若一个无序数组中的各个元素各不相同，要求用二分法找到这个无序数组中的局部最小点，其中局部最小的含义是，这个位置上的前后位置元素都比这个位置上的元素数值大
。
比如说有一个数组arr = {1, 16, 15, 9, 7, 8, 11, 12, 7}，那么明显，这个数组中的元素7，对应下标为4的位置是局部最小点，因为它的前后位置对应元素为9和8，都比它大。
问题思路
用反证法可以证明，若一个所有元素都不同的数组，它的起始两个元素和最后的两个元素满足关系：
a
r
r
[
0
]
>
a
r
r
[
1
]
a
n
d
a
r
r
[
n
−
2
]
<
a
r
r
[
n
−
1
]
arr[0]>arr[1] \ and \ arr[n-2] < arr[n-1]
a
rr
[
0
]
>
a
rr
[
1
]
an
d
a
rr
[
n
−
2
]
<
a
rr
[
n
−
1
]
那么这个数组之间一定存在局部最小值，根据这个结论就可以采用二分法寻找局部最小，且我们将首末两个元素当作特殊情况考虑，使得问题变得比较简单，具体解释见以下代码。
代码实现
// 二分法查找无重复元素无序数组的局部最小值
int BinSearch_ForLocalMinimum(const vector<int>& arr)
{
// 初始化3个Index
int lowIndex = 0;
int highIndex = arr.size() - 1;
int midIndex = (lowIndex + highIndex) / 2;
// 两种特殊情况，即对首末元素的讨论
if (arr[0] < arr[1])
{
// 由于arr[0]是边界值，它左边不可能存在元素，所以此时arr[0]就是局部最小值
return 0;
}
if (*(arr.rbegin() + 1) > *arr.rbegin())
{
// 同理，由于arr的最后一个元素是边界值，它右边不可能存在元素，所以此时*arr.rbegin()就是局部最小值
return arr.size() - 1;
}
// 除开上面两种特殊情况，那么此时数组就是a[0]>a[1] && a[n-2]<a[n-1]，那么a[0 ~ n-1]之间一定存在局部最小值
while (lowIndex < highIndex)
{
if (arr[midIndex - 1] > arr[midIndex] && arr[midIndex] < arr[midIndex + 1])
{
// 满足局部最小条件，直接返回
return midIndex;
}
else if (arr[midIndex] > arr[midIndex - 1])
{
// 说明当前mid位置元素比前一个位置大，那么此时向前二分，即a[low]>a[low+1] && a[mid-1]<a[mid]
highIndex = midIndex;
}
else if (arr[midIndex] > arr[midIndex + 1])
{
// 说明当前mid位置元素比后一个元素大，那么此时向后二分，即a[mid]>a[mid+1] && a[high-1]<a[high]
lowIndex = midIndex;
}
midIndex = (lowIndex + highIndex) / 2;
}
// 经过上述的查找，基于原本对数组无重复元素的要求，必然可以得到结果，不存在找不到的情况。
}
void main()
{
// 一般情况测试
vector<int> arr1{ 25,17,16,15,14,13,15,17,18,19,20,21 };
int localMinIndex1 = BinSearch_ForLocalMinimum(arr1);
cout << "局部最小值所在位置：" << localMinIndex1 <<"，局部最小值：" << arr1[localMinIndex1] << endl;
// 下边界条件测试
vector<int> arr2{ 30,17,18,19,20,21,23,24,25,26,27,28 };
int localMinIndex2 = BinSearch_ForLocalMinimum(arr2);
cout << "局部最小值所在位置：" << localMinIndex2 << "，局部最小值：" << arr2[localMinIndex2] << endl;
// 上边界条件测试
vector<int> arr3{ 38,37,36,35,34,33,32,31,30,29,27,28 };
int localMinIndex3 = BinSearch_ForLocalMinimum(arr3);
cout << "局部最小值所在位置：" << localMinIndex3 << "，局部最小值：" << arr3[localMinIndex3] << endl;
system("pause");
}