什么是二分查找

二分查找的基本原则

三大模板

查找元素的第一个下标

private int findFirst(int[] nums, int target){
    int left = 0, right = nums.length-1;
    while(left<right){
        int mid = left + (right - left)/2;
        // mid左边元素被排除，left = mid + 1
        if(nums[mid] < target){
            left = mid + 1;
        }else{
            right = mid;
        }
    }
    return left;
}

查找元素的最后一个下标

private int findLast(int[] nums, int target){
    // 避免死循环
    int left = 0, right = nums.length-1;
    while(left<right){
        int mid = left + (right - left + 1)/2;
        // mid右边元素被排除，right = mid - 1
        if(nums[mid] > target){
            right = mid - 1;
        }else{
            left = mid;
        }
    }
    return left;
}

注意：mid = L+(R-L+1)/2 对于偶数个数，会停在中间右侧，而mid = L+(R-L)/2会停在中间左侧

注意：return k-arr[l]<arr[r]-k?l:r; 谁的结果更接近于0，则选择谁。