1.二分查找
https://leetcode.cn/problems/binary-search/
思路
标准的二分查找。给定一个有序数组和目标值，每次选择数组的中间元素与目标值比较。如果中间元素等于目标值，则返回该索引；若中间元素小于目标值，则在右侧继续搜索；若中间元素大于目标值，则在左侧继续搜索。时间复杂度为 O(log n)。
步骤
初始化：设置 left 和 right 分别为数组的开头和结尾。 二分查找：计算中点 mid。 如果 nums[mid] 等于目标值，返回 mid。 如果 nums[mid] 小于目标值，更新 left = mid + 1。 如果 nums[mid] 大于目标值，更新 right = mid - 1。 终止条件：如果没有找到，返回 -1。
class Solution {
public:
int search(vector<int>& nums, int target) {
int n = nums.size(); // 获取数组的大小
// 定义左右边界，left 是左边界，right 是右边界
for (int left = 0, right = n - 1; left <= right;) {
// 计算中间索引 mid，避免溢出的安全写法可以使用：mid = left + (right - left) / 2;
int mid = (left + right) / 2;
// 如果中间值小于目标值，说明目标值在右半部分，移动左边界到 mid + 1
if (nums[mid] < target) left = mid + 1;
// 如果中间值大于目标值，说明目标值在左半部分，移动右边界到 mid - 1
if (nums[mid] > target) right = mid - 1;
// 如果中间值等于目标值，返回当前中间值的索引
if (nums[mid] == target) return mid;
}
// 如果没有找到目标值，返回 -1
return -1;
}
};
2.在排序数组中查找元素的第一个和最后一个位置
https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/
思路
这是经典的'查找范围'问题，可以用两次二分查找解决。第一次找第一个出现位置，第二次找最后一个出现位置。时间复杂度为 O(log n)，适合处理排序数组。
步骤
查找第一个位置：使用二分查找，找到目标值的第一个位置。 每次判断 nums[mid] 是否大于等于 target，是则向左移动，否则向右移动。 查找最后一个位置：使用二分查找，找到目标值的最后一个位置。 每次判断 nums[mid] 是否小于等于 target，是则向右移动，否则向左移动。 返回结果：如果找到两个位置，返回它们的范围，否则返回 [-1, -1]。
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
// 如果数组为空，直接返回 {-1, -1}
if (nums.size() == 0) return {-1, -1};
// 获取数组的大小
int n = nums.size();
// 初始化左右边界
int left = 0, right = n - 1;
// 查找左端点，目标是找到 target 第一次出现的位置
while (left < right) {
// 计算中间索引，防止溢出的安全写法
int mid = left + (right - left) / 2;
// 如果中间值小于目标值，说明目标值在右侧，将 left 移到 mid + 1
if (nums[mid] < target) left = mid + 1;
// 如果中间值大于等于目标值，右边界移动到 mid，继续查找
if (nums[mid] >= target) right = mid;
}
// 如果左边界的值不等于 target，说明数组中没有该值，返回 {-1, -1}
if (nums[left] != target) return {-1, -1};
// 记录找到的目标值的起始位置
int begin = left;
// 查找右端点，目标是找到 target 最后一次出现的位置
right = n - 1;
// 重新初始化右边界
// 使用二分查找找右边界
while (left < right) {
// 计算中间索引，为了确保 mid 偏向右侧，加 1
int mid = left + (right - left + ) / ;
(nums[mid] <= target) left = mid;
(nums[mid] > target) right = mid - ;
}
{begin, right};
}
};
3.x 的平方根
https://leetcode.cn/problems/sqrtx/
思路
使用二分查找法求 x 的平方根。定义初始范围为 0,x，每次取中间值 m，计算 m²与 x 的比较。如果 m²小于 x，则移动左边界；如果 m²大于 x，则移动右边界。直至找到平方根或其整数部分。
步骤
初始化：设置 left 为 0，right 为 x。 二分查找：计算中点 mid。 如果 mid * mid 小于 x，说明平方根在右侧，更新 left = mid + 1。 如果 mid * mid 大于 x，说明平方根在左侧，更新 right = mid - 1。 终止条件：当 left 和 right 相遇时，取较小值作为结果的整数部分。
class Solution {
public:
int mySqrt(int x) {
// 定义二分查找的左右边界
int left = 1, right = x;
// 如果 x 小于 1，直接返回 0
if (x < 1) return 0;
// 开始二分查找
while (left < right) {
// 计算中间值，为了避免溢出，使用 left + (right - left + 1) / 2
long long mid = left + (right - left + 1) / 2;
// 如果 mid 的平方小于等于 x，说明 mid 可能是答案，或者答案在右侧，将 left 移动到 mid
if (mid * mid <= x) left = mid;
// 如果 mid 的平方大于 x，说明 mid 太大，答案在左侧，将 right 移动到 mid - 1
else if (mid * mid > x) right = mid - 1;
}
// 返回找到的平方根的整数部分
return left;
}
};
4.搜索插入位置
https://leetcode.cn/problems/search-insert-position/description/
思路
给定一个有序数组和目标值，要求返回目标值在数组中的插入位置。如果数组中存在目标值，返回其索引；若不存在，返回其应该插入的位置。使用二分查找，找到第一个大于或等于目标值的位置。
步骤
初始化：使用 left 和 right 指针。 二分查找：计算中点 mid。 如果 nums[mid] 大于或等于目标值 target，则将 right 更新为 mid - 1。 否则，将 left 更新为 mid + 1。 终止条件：当 left 和 right 相遇时，left 即为目标值要插入的位置。
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int n = nums.size(); // 获取数组的大小
// 定义左右边界，left 是左边界，right 是右边界
int left = 0, right = n - 1;
while (left <= right) {
// 计算中间索引 mid，避免溢出的安全写法
int mid = left + (right - left) / 2;
// 如果中间值小于目标值，说明目标值在右半部分，移动左边界到 mid + 1
if (nums[mid] < target) left = mid + 1;
// 如果中间值大于目标值，说明目标值在左半部分，移动右边界到 mid - 1
if (nums[mid] > target) right = mid - 1;
// 如果中间值等于目标值，返回当前中间值的索引
if (nums[mid] == target) return mid;
}
// 如果没有找到目标值，返回插入位置 left
return left;
}
};
5.山脉数组的峰顶索引
https://leetcode.cn/problems/peak-index-in-a-mountain-array/
思路
山脉数组是先递增后递减的数组，因此其峰顶就是数组中最大值的位置。可以使用二分查找，类似'寻找峰值'的思路，找到这个峰顶索引。
步骤
初始化：使用 left 和 right 指针，分别指向数组的开头和结尾。 二分查找：计算中点 mid。 如果 nums[mid] 大于 nums[mid + 1]，峰顶在左侧，更新 right = mid。 如果 nums[mid] 小于 nums[mid + 1]，峰顶在右侧，更新 left = mid + 1。 终止条件：当 left 和 right 相遇时，left 即为峰顶的索引。
class Solution {
public:
int peakIndexInMountainArray(vector<int>& arr) {
// 获取数组大小
int n = arr.size();
// 定义左右边界。由于数组两端不能是峰值，山峰一定在 1 到 n-2 之间
int left = 1, right = n - 2;
// 当左边界小于右边界时，继续查找
while (left < right) {
// 计算中间位置，使用 left + (right - left + 1) / 2 可以避免溢出
int mid = left + (right - left + 1) / 2;
// 如果中间元素比左侧的前一个元素小，说明山峰在左边，右边界移动到 mid - 1
if (arr[mid] < arr[mid - 1]) right = mid - 1;
// 否则，山峰在右侧或当前位置，左边界移动到 mid
else left = mid;
}
// 循环结束时，left 和 right 会指向同一个位置，这就是峰值的索引
return left;
}
};
6.寻找峰值
https://leetcode.cn/problems/find-peak-element/description/
思路
峰值定义为该元素比相邻元素大。可以使用二分查找的变种。每次选择中点，如果中点比其右侧元素小，则峰值在右侧；如果中点比其右侧元素大，则峰值在左侧。这样逐步缩小搜索范围，直至找到峰值。
步骤
初始化：定义 left 和 right 指针。 二分查找：每次计算中点 mid。 如果 nums[mid] 大于 nums[mid + 1]，说明峰值在左侧或就是 mid，更新 right = mid。 如果 nums[mid] 小于 nums[mid + 1]，说明峰值在右侧，更新 left = mid + 1。 终止条件：当 left 和 right 相遇时，left 即为峰值所在的位置。
class Solution {
public:
int findPeakElement(vector<int>& nums) {
// 初始化左右边界
int left = 0, right = nums.size() - 1;
// 二分查找
while (left < right) {
// 计算中间索引，避免溢出
int mid = left + (right - left) / 2;
// 如果中间值大于它右边的元素，说明峰值在左侧或当前元素是峰值，将右边界移到 mid
if (nums[mid] > nums[mid + 1]) right = mid;
// 如果中间值小于它右边的元素，说明峰值在右侧，将左边界移到 mid + 1
else left = mid + 1;
}
// 返回最终找到的峰值索引
return left;
}
};
7.寻找旋转排序数组中的最小值
https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/description/
思路
旋转排序数组的特点是其包含两个有序的子数组（前一段大于后一段）。最小值通常出现在这两个有序子数组的交界处。可以使用二分查找，比较中点和右端点的值，若中点大于右端点，最小值在右侧；若中点小于右端点，最小值在左侧。
步骤
初始化：定义 left 和 right 指针。 二分查找：每次计算中点 mid。 如果 nums[mid] 大于 nums[right]，说明最小值在右侧，更新 left = mid + 1。 否则，最小值在左侧或当前 mid 处，更新 right = mid。 终止条件：当 left 和 right 相遇时，left 即为最小值所在的位置。
class Solution {
public:
int findMin(vector<int>& nums) {
int n = nums.size(); // 获取数组大小
int left = 0, right = n - 1; // 初始化左右边界
// 二分查找
while (left < right) {
int mid = left + (right - left) / 2; // 计算中间索引，避免溢出
// 如果中间值大于最右侧值，说明最小值在右侧，更新 left
if (nums[mid] > nums[right]) left = mid + 1;
// 否则，最小值在左侧或当前 mid 处
else right = mid;
}
// 最小值在 left 处
return nums[left];
}
};
8.JZ53(2) 缺失的数字
《剑指 offer 面试题 53-II》 题目类型：0〜n-1 中缺失的数字（面试题 53 - II） 因为这题作者在 leetcode 中未找到这题原题，不过有一道类似题目 （这题在 leetcode 消失的原因是剑指 offer 在 leetcode 上下架了） https://leetcode.cn/problems/que-shi-de-shu-zi-lcof/
思路
因为数组是排好序的，且数字从 0 到 n-1 连续，可以使用二分查找找到缺失的数字。如果 nums[mid] == mid，说明缺失的数字在右侧；否则在左侧。
class Solution {
public:
// 该函数通过二分查找处理缺失数字问题，返回缺失的数字
int missingNumber(vector<int>& records) {
// 初始化左右边界
int left = 0, right = records.size() - 1;
// 执行二分查找
while (left < right) {
// 计算中间索引，避免溢出
int mid = left + (right - left) / 2;
// 如果记录值等于索引值，继续在右侧查找
if (records[mid] == mid) left = mid + 1;
// 否则缩小右侧边界
else right = mid;
}
// 如果最终找到的位置的索引值等于该位置的记录值，则返回 left + 1，否则返回 left
return left == records[left] ? left + 1 : left;
}
};
此外这题还可以用 4 种 O(n) 时间复杂度方法去求：第 1 种：直接遍历寻找，第 2 种：哈希，第 3 种：异或，第 4 种：等差求和。
