代码随想录第一章数组704.二分查找

代码随想录 第一章 数组 704.二分查找 题目： 题目链接：704. 二分查找题目描述：给定一个 n​ 个元素有序的（升序）整型数组 nums​ 和一个目标值 target​ ，写一个函数搜索 nums​ 中的 target​，如果目标值存在返回下标，否则返回 -1​。 一、思想

二分查找算法的核心思想是 分治策略，通过 有序数组的有序性 快速缩小搜索范围。具体实现要点：

有序性前提：数组必须有序（本问题为升序），这是二分查找的根基区间收敛：通过不断将搜索区间 对半分割，利用中间值与目标值的比较结果，将搜索范围缩小到左半区或右半区终止条件：当搜索区间缩小为空（左指针超过右指针）时确定目标不存在 二、代码 // 左闭右闭的写法 class Solution { public: /** * @brief 二分查找算法实现 * @param nums 已排序的整型数组（升序排列） * @param target 需要查找的目标值 * @return 目标值在数组中的索引，未找到返回-1 * @note 二分查找的前提是数组已经是有序的，本函数对有序数组进行二分查找 */ int search(vector<int> &nums, int target) { // 初始化双指针：左边界和右边界 int left = 0; // 搜索区间的左端点 int right = nums.size() - 1; // 搜索区间的右端点 // 循环终止条件：当左指针超过右指针时说明搜索区间已空 while (left <= right) { // 计算中间索引（防止整数溢出的安全写法） // 等同于 (left + right)/2，但避免两数相加可能导致的溢出 int mid = left + (right - left) / 2; // 找到目标值的三种情况处理 if (nums[mid] == target) { return mid; // 直接返回找到的索引位置 } // 中间值小于目标值时：收缩左边界 else if (nums[mid] < target) { left = mid + 1; // +1 排除已检查的mid位置 } // 中间值大于目标值时：收缩右边界 else { right = mid - 1; // -1 排除已检查的mid位置 } } // 遍历完整个搜索区间未找到目标值 return -1; // 返回标准未找到标识 } }; 三、解析 算法工作原理分解

初始化区间：定义 left=0​, right=size-1​，覆盖整个数组范围

循环分割：

计算中间点 mid = left + (right - left)/2​ （等价于 (left+right)/2​，但避免 left+right​ 整数溢出）若 nums[mid] == target​：直接命中目标，返回索引若 nums[mid] < target​：目标在右半区，调整左边界 left = mid + 1​若 nums[mid] > target​：目标在左半区，调整右边界 right = mid - 1​

终止判断：当 left > right​ 时说明区间已空，返回 -1​

关键点说明 循环条件 ​left <= right​​ 允许 left == right​ 时进入循环处理单个元素的情况，避免漏判边界更新逻辑 每次排除已检查的 mid​ 位置（+1/-1​），确保搜索区间严格缩小，避免死循环整数溢出防御 ​mid = left + (right - left)/2​ 写法可避免 left + right​ 超过 INT_MAX​ 的风险 其他写法 区间类型循环条件边界更新规则典型应用场景左闭右闭​left <= right​​left=mid+1​ right=mid-1​标准二分查找左闭右开​left < right​​left=mid+1​ right=mid​动态数组、插入位置左开右闭​left < right​​left=mid​ right=mid-1​特殊条件判断 四、复杂度分析 时间复杂度：O(log n) 每次循环将搜索区间减半，最坏情况下需要 log₂n 次比较（n为数组长度）空间复杂度：O(1) 仅需常数级别的额外空间存储指针变量（left/right/mid）

‍