二分查找算法

 感谢“五点七边”工作室的算法讲解，详细内容可以参考视频讲解

二分查找为什么总是写错？_哔哩哔哩_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. 在排序数组中查找元素的第一个和最后一个位置