二分查找算法
感谢“五点七边”工作室的算法讲解，详细内容可以参考视频讲解
二分查找为什么总是写错？_哔哩哔哩_bilibili
此处仅是个人学习总结
以target等于5为例，输入: 1 2 3 5 5 5 8 9
| 1. 找到第一个 >= target 的元素 |
| |
| 判断条件 < target，返回r (C++ 对应std:: lower_bound()) | ||
| 2. 找到最后一个 < target 的元素 |
| |
| 判断条件 < target, 返回l (C++ 对应std:: lower_bound() - 1) | ||
| 3. 找到第一个 > target 的元素 |
| |
| 判断条件 <= target，返回r (C++ 对应std:: uper_bound()) | ||
| 4. 找到最后一个 <= target 的元素 |
| |
| 判断条件 <= target，返回l (C++ 对应std:: uper_bound() - 1) | ||
static int BinarySearch(int datas[], int num, int target)
{int left = -1;int right = num;int mid;while ((left + 1) != right) {mid = ((right - left) >> 1) + left;if (判断条件) {left = mid;} else {right = mid;}}return left or right;
}练习题
34. 在排序数组中查找元素的第一个和最后一个位置