【代码随想录刷题记录】LeetCode704二分查找

读研以后写AI那些玩意写多了，确实需要练练算法，我现在写个二分查找都出现问题，绷不住了，而且过CSP竞赛是毕业条件，没办法，以后一天刷一个题吧，太忙了

1. 左闭右闭

class Solution {
public:
    //左闭右闭
    int search(vector<int>& nums, int target) {
        int left = 0; //最左侧下标
        int right = nums.size() - 1; //最右侧下标
        /*注意！！！求解中点是不断地求解，不是求解一次就完成了，
        我一开始把求解中点写到循环外了，这是错误的*/
        //（错误）int middle = ((right - left) >> 1) + left; //求解中点下标
        // 两边都能取到，所以用小于等于
        while(left <= right)
        {
            // 中点的判断条件是right - left（区间长度）除2（相当于右移1位）再加left（因为区间不一定是从0开始的）
            int middle = ((right - left) >> 1) + left; //求解中点下标
            //如果中间值就是target，直接返回中间下标
            if(target == nums[middle])
            {
                return middle;
            }
            //如果target大于中间值，向右子列寻找，则left变成middle+1
            else if(target > nums[middle])
            {
                left = middle + 1;
            }
            //如果target小于中间值，向左子列寻找，则right变为middle-1（因为是左闭右闭，闭合包括区间端点，所以需要抠除middle）
            else
            {
                right = middle - 1;
            }
        }
        //都过一遍没找到，返回-1
        return -1;
    }
};

2. 左闭右开

class Solution {
public:
    //左闭右开
    int search(vector<int>& nums, int target) {
        int left = 0; //最左侧下标
        int right = nums.size(); //这儿一开始我写错了，还以为是nums.size()，右侧是开区间取不到端点，可以直接用nums的size，相当于最后一个元素下标+1
        //左闭右开
        while(left < right)
        {
            // 中点的判断条件是right - left（区间长度）除2（相当于右移1位）再加left（因为区间不一定是从0开始的）
            int middle = ((right - left) >> 1) + left; //求解中点下标
            //如果中间值就是target，直接返回中间下标
            if(target == nums[middle])
            {
                return middle;
            }
            //如果target大于中间值，向右子列寻找，则left变成middle+1
            else if(target > nums[middle])
            {
                left = middle + 1;
            }
            //如果target小于中间值，向左子列寻找，则right变为middle（因为是左闭右开，开区间不包括区间端点，所以直接是middle）
            else
            {
                right = middle;
            }
        }
        //都过一遍没找到，返回-1
        return -1;
    }
};