10.1 二分查找

折半查找 704. 二分查找 - 力扣（LeetCode）

35. 搜索插入位置 - 力扣（LeetCode）

34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode） 10.3   二分查找边界 - Hello 算法 (hello-algo.com)

由于 𝑖 和 𝑗 都是 int 类型，因此 𝑖+𝑗 可能会超出 int 类型的取值范围。为了避免大数越界，通常采用公式 \(𝑚=⌊𝑖+(𝑗−𝑖)/2⌋\) 来计算中点 1. (𝑗−𝑖)：计算索引距离 2. (𝑗−𝑖)/2：计算距离的一半 3. 𝑚=⌊𝑖+(𝑗−𝑖)/2⌋：将距离的一半加到起始索引i上，得到中点

C语言中，整数除以另一个整数时，结果会自动向下取整（即舍弃小数部分）

//二分查找
int search(int* nums, int numsSize, int target) {
    int left = 0;
    //长度-1为数组索引最后一位
    int right = numsSize - 1;

    while(left <= right){

        int mid = left + (right - left) / 2;

        if(nums[mid] < target)
            left = mid + 1;
        else if(nums[mid] > target)
            right = mid - 1;
        else
            return mid;
    }
    return -1;
}

//二分查找插入点
int searchInsert(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)
            left = mid + 1;
        else if(nums[mid] > target)
            right = mid - 1;
        else
            return mid;
    }
    //倘若元素不存在，当二分查找结束，left会指向第一个大于目标值的位置
    return left;
}