力扣704. 二分查找

class Solution {
public:
    int search(vector<int>& nums, int target) {
        //此种二分写法是将target放在一个左闭右闭的区间里，也就是[left,right]中
        //所以令left指向数组的第一个元素的下标位置，令right在数组最后一个元素的下标的位置。
        int n = nums.size();
        int left = 0;
        int right = n-1;
        int mid = 0;    //中间元素的下标，定义在while循环外面是为避免频繁的创建，因为在while循环里面，每一次循环的开始都要确定mid的大小。
        //<=是因为left = right是有意义的。
        while(left <= right){
            //相当于mid = (left + right) / 2，应尽量不这样写，因为当left和right数值很大的时候，相加可能会造成数据的溢出。
            mid = (right - left) /2 + left;
            //如果当前mid处的元素值正好等于target的话，直接返回mid
            if(nums[mid] == target){
                return mid;
            }
            //如果当前mid处的元素值大于target的话，那么说明要找的目标值在mid的左侧，所以将right-1
            else if(nums[mid] > target){
                right = mid - 1;
                continue;
            }
            //如果当前mid处的元素值小于target的话，那么说明要找的目标值在mid的右侧，所以将left-1
            else{
                left = mid + 1;
                continue;
            }
        }
        //此种情况说明目标值不在nums数组中，所以返回-1
        return -1;
    }
    //时间复杂度：O(logn)，其中 n 是数组的长度。
    //空间复杂度：O(1)。
};