算法训练营第一天 704. 二分查找

第 1 天 数组基础及二分查找

今日任务：先把 704写熟练，要熟悉 根据 左闭右开，左闭右闭 两种区间规则 写出来的二分法。
题目建议： 了解一下数组基础，以及数组的内存空间地址，数组也没那么简单。
题目链接：https://leetcode.cn/problems/binary-search/
视频讲解：https://www.bilibili.com/video/BV1fA4y1o715

二分查找算法
二分查找通过不断缩小搜索范围来快速定位目标值。具体步骤如下：

初始化左边界 left 为 0，右边界 right 为数组长度减 1。

在每次迭代中，计算中间位置 mid，并比较 nums[mid] 与目标值 target：

若 nums[mid] == target，直接返回 mid。
若 nums[mid] < target，说明目标值在右半部分，调整左边界 left = mid + 1。
若 nums[mid] > target，说明目标值在左半部分，调整右边界 right = mid - 1。
重复上述过程直到找到目标值或搜索范围为空（即 left > right），此时返回 -1。

int search(int* nums, int numsSize, int target) {
    int left = 0;
    int right = numsSize - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2; // 防止溢出
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return -1;
}

防止溢出：计算 mid 时使用 left + (right - left) / 2 而非 (left + right) / 2，避免 left + right 超出整数范围。
边界条件：循环条件为 left <= right，确保能处理边界情况（如数组仅有一个元素）。
时间复杂度：每次迭代将搜索范围减半，时间复杂度为 O(log n)，满足题目要求。