Binary Search

private int binarySearch(int[] nums, int target){
    int l = 0, r = nums.length - 1;
    while(l <= r){
        int mid = l + (r - l) / 2;
        if(nums[mid] >= target){
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    // if target exists in the nums, check nums[l] == target, l is the most left position
    // if target not exist in the nums, nums[l] > target, l is the first element greater than target(l maybe out of index)
    return l;
}

private int binarySearch(int[] nums, int target){
    int l = 0, r = nums.length - 1;
    while(l <= r){
        int mid = l + (r - l) / 2;
        if(nums[mid] <= target){
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    // if target exists in the nums, check nums[r] == target, r is the most right position
    // if target not exist in the nums, nums[r] < target, r is the last element less than target(r maybe out of index)
    return r;
}