https://leetcode.cn/problems/binary-search/description/

<aside> 💡

思路重点：区间的定义——是左闭右闭还是左闭右开？

· 右开还是右闭决定了right指向的值能否被访问

区间的定义回答了以下问题：

1、right的初始值是nums.size()还是nums.size()-1？

2、循环条件是left < right还是left <= right？

3、left与right如何更新，如：right的更新是right = middle还是right = middle - 1？

</aside>

左闭右开写法

int search(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size();        // 初始值等于size

    while (left < right) {
        int middle = (left + right) / 2;
        if (nums[middle] == target)
            return middle;
        else if (nums[middle] > target) {
            right = middle;         // 右开，所以直接等于middle
        }
        else {
            left = middle + 1;
        }
    }
    return -1;
}

左闭右闭写法

int search(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;

    // 右闭时条件为<=
    while (left <= right) {
        //int middle = (left + right) / 2;          // 这样的写法可能int越界
        int middle = left + (right - left) / 2;
        if (nums[middle] == target)
            return middle;
        else if (nums[middle] > target) {
            right = middle - 1;      // 右闭时，middle不应该在搜索区间内
        }
        else {
            left = middle + 1;
        }
    }
    return -1;
}