Count of Smaller Numbers After Self

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example:

Input: [5,2,6,1]
Output: [2,1,1,0] 
Explanation:
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

这道题给定我们一个数组，让我们计算每个数字右边所有小于这个数字的个数，目测我们不能用brute force，OJ肯定不答应，那么我们为了提高运算效率，首先可以使用用二分搜索法，思路是将给定数组从最后一个开始，用二分法插入到一个新的数组，这样新数组就是有序的，那么此时该数字在新数组中的坐标就是原数组中其右边所有较小数字的个数，

这道题list一开始没有值，就算有值 也是0， 往里插数字后，不是从小到大排列的，违背了二分搜索原则，于是对储存数组值得那个list进行赋予最大值操作

class Solution {
    public List<Integer> countSmaller(int[] nums) {
        
        List<Integer> results = new ArrayList<>();
        
        if(nums == null || nums.length == 0)
            return results;
        
        List<Integer> list = new ArrayList<>();
        for(int i = 0 ; i < nums.length; i++){
            list.add(Integer.MAX_VALUE);
        }
        
        int[] res = new int[nums.length];
        //iterator from end of nums
        
        for(int i = nums.length -1 ; i >= 0; i--){
            int index = binarySearch(list,nums[i]);
            System.out.println(index);
            res[i] = index;
            list.add(index,nums[i]);
        }
        
        
        for(int i = 0; i < res.length; i++){
            results.add(res[i]);
        }
        return results;
    }
    
    public int binarySearch(List<Integer> list, int target){
        if(list.size() == 0){
            return 0;
        }
        
        int start = 0, end = list.size() -1 ;
        
        while(start + 1 < end){
            int mid = start + (end - start)/2;
            
            if(list.get(mid) < target){
                start = mid;
            }else{
                end = mid;
            }
        }
        if(list.get(start) >= target){
            return start;
        }
        if(list.get(end) >= target){
            return end;
        }
        
        return 0;
        
    }
}