二分查找

二分查找的区间定义

参考：二分查找的区间到底是开还是闭？

• 左开右开 (left,right)
• 左闭右闭 [left,right]
• 左开右闭 (left,right]
• 左闭右开 [left,right)

通常来说，我们一般会选择【左闭右开】或者【左闭右闭】的区间定义。

左闭右闭区间

• 定义：搜索区间包括 left 和 right，即 left 和 right 都可能是目标值。
• 退出条件：left > right，表示搜索区间为空。
• 左闭右闭区间的二分查找的常见写法如下：

while (left <= right) { // 注意是 <=
    int mid = left + (right - left) / 2;
    if (nums[mid] == target) {
        return mid;
    } else if (nums[mid] < target) {
        left = mid + 1; // [mid+1, right]
    } else {
        right = mid - 1; // [left, mid-1]
    }
}

左闭右开区间

• 定义：搜索区间包括 left 但不包括 right，即目标值可能是 left，但不可能是 right。
• 退出条件：当 left == right 时，表示搜索区间为空。
• 左闭右开区间的二分查找的常见写法如下：

while (left < right) { // 注意是 <
    int mid = left + (right - left) / 2;
    if (nums[mid] == target) {
        return mid;
    } else if (nums[mid] < target) {
        left = mid + 1; // [mid+1, right)
    } else {
        right = mid; // [left, mid)
    }
}