二分查找算法的基本思想及应用场景，涵盖二分答案、二分区间和二分浮点数三种类型。通过四个 LeetCode 经典例题（二分查找、在排序数组中查找元素的第一个和最后一个位置、搜索插入位置、x 的平方根），详细讲解了题目分析、实现思路及 C++ 代码实现。重点阐述了左右边界查找、取整技巧及时间复杂度优化至 O(log n) 的方法，适合算法初学者入门。
二分算法是算法题目中常见的一种优化算法，很好地体现了分治的思想。该算法不仅在算法题目中屡见不鲜，在实际工程中也十分热门，例如数据库索引、文件系统以及游戏 AI 的路径规划等。常见的二分算法类型包括二分答案、二分区间和二分浮点数。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online
二分答案：在有单调性的区间中找值，通过二分思想调整查找范围。
二分区间：搜索一个区间而非单个值，常应用于在区间内查找某一个解的情况。
二分浮点数：处理方式略有不同，但核心思想类似二分答案。
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target，写一个函数搜索 nums 中的 target。如果 target 存在返回下标，否则返回 -1。必须编写一个具有 O(log n) 时间复杂度的算法。
示例 1:
输入：nums = [-1,0,3,5,9,12], target = 9
输出：4
解释：9 出现在 nums 中并且下标为 4
示例 2:
输入：nums = [-1,0,3,5,9,12], target = 2
输出：-1
解释：2 不存在 nums 中因此返回 -1
提示：
nums 中的所有元素是不重复的。n 将在 [1, 10000] 之间。nums 的每个元素都将在 [-9999, 9999] 之间。这是一道经典的二分答案题目，核心思想就是二分。
定义两个指针，左指针 left 和右指针 right，分别指向数组的左右端点，计算中间点 mid。讨论三种情况：
nums[mid] == target：说明找到了，直接返回。nums[mid] > target：说明区间 [mid, right] 的值都大于 target，舍弃该区间，在左边 [left, mid - 1] 继续查找，即 right = mid - 1。nums[mid] < target：说明区间 [left, mid] 的值都小于 target，舍弃该区间，在右边 [mid + 1, right] 继续查找，即 left = mid + 1。以上操作在 while(left <= right) 条件下进行，跳出循环说明未找到。
class Solution {
public:
int search(vector<int>& nums, int target) {
int n = nums.size();
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left + 1) / 2;
if (nums[mid] < target) left = mid + 1;
else if (nums[mid] > target) right = mid - 1;
else return mid;
}
return -1;
}
};
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。如果不存在，返回 [-1, -1]。必须设计并实现时间复杂度为 O(log n) 的算法。
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例 2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
示例 3：
输入：nums = [], target = 0
输出：[-1,-1]
提示：
0 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^9nums 是一个非递减数组-10^9 <= target <= 10^9这是二分区间的经典例题。基础二分模板保留特定左或右下标的方式可能找不到等于 target 的值，这里需要确保找到的是等于 target 的边界。
分别找到左边界和右边界。
找左边界：
明确区间特点：左区间 [left, k - 1] 小于 target，右区间 [k, right] 大于等于 target。
mid 在 [left, k - 1] 时，nums[mid] < target，舍弃 [left, mid]，更新 left = mid + 1。mid 在 [k, right] 时，nums[mid] >= target，不能舍弃 k，舍弃 [left + 1, right]，更新 right = mid。
注意：此处需向下取整，避免死循环。找右边界：
明确区间特点：左区间 [left, k] 小于等于 target，右区间 [k + 1, right] 大于 target。
mid 在 [left, k] 时，nums[mid] <= target，不能舍弃 mid，舍弃 [left, mid - 1]，更新 left = mid。mid 在 [k + 1, right] 时，nums[mid] > target，舍弃 [mid, right]，更新 right = mid - 1。
注意：此处需向上取整。class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int n = nums.size();
if (n == 0) return {-1, -1};
// 找左边界
int left = 0, right = n - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) left = mid + 1;
else right = mid;
}
int Left = 0;
if (nums[left] != target) return {-1, -1};
else Left = left;
// 找右边界
left = 0; right = n - 1;
while (left < right) {
int mid = left + (right - left + 1) / 2;
if (nums[mid] <= target) left = mid;
else right = mid - 1;
}
return {Left, left};
}
};
这里给一个取整的小技巧：while 循环里有
-1，取整就要+1；反之则没有+1。
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入：nums = [1,3,5,6], target = 5
输出：2
示例 2:
输入：nums = [1,3,5,6], target = 2
输出：1
示例 3:
输入：nums = [1,3,5,6], target = 7
输出：4
提示：
1 <= nums.length <= 10^4-10^4 <= nums[i] <= 10^4nums 为无重复元素的升序排列数组-10^4 <= target <= 10^4该题目可转换为找出大于等于目标值的最左端，复用之前写的代码。
使用二分基础模板，标记大于等于目标值的下标。
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int ret = -1;
int left = 0, right = nums.size() - 1;
if (nums[nums.size() - 1] < target) return nums.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) left = mid + 1;
else right = mid;
}
return left;
}
};
class Solution {
public:
int searchInsert(vector<int>& a, int value) {
int L = 0;
int R = a.size() - 1;
if (a[a.size() - 1] < value) return a.size();
int index = -1;
while (L <= R) {
int mid = L + ((R - L + 1) >> 1);
if (a[mid] >= value) {
index = mid;
R = mid - 1;
} else {
L = mid + 1;
}
}
return index;
}
};
给你一个非负整数 x，计算并返回 x 的算术平方根。由于返回类型是整数，结果只保留整数部分，小数部分将被舍去。不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5。
示例 1：
输入：x = 4
输出：2
示例 2：
输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
提示：
0 <= x <= 2^31 - 1实际求的是小于等于根号 x 的最大值，可复用第二题或第三题的代码二。
条件改变，基本思路一致。
class Solution {
public:
int mySqrt(int x) {
int left = 1, right = x;
if (x < 1) return 0;
while (left < right) {
long long mid = left + (right - left + 1) / 2;
if (mid * mid <= x) left = mid;
else right = mid - 1;
}
return left;
}
};
class Solution {
public:
int mySqrt(int x) {
int left = 1, right = x;
if (x < 1) return 0;
int index = -1;
while (left <= right) {
long long mid = left + (right - left + 1) / 2;
if (mid * mid <= x) {
index = mid;
left = mid + 1;
} else right = mid - 1;
}
return index;
}
};