Count of Smaller Number before itself

Give you an integer array (index from 0 to n-1, where n is the size of this array, value from 0 to 10000) . For each element Ai in the array, count the number of element before this element Ai is smaller than it and return count number array.

Example

For array [1,2,7,8,5], return [0,1,2,3,2]

Notes:

1. Binary Search the previous result
2. Find the insertion position and at the same time return the smaller counts
3. Be careful about the corner cases

  public ArrayList<Integer> countOfSmallerNumberII(int[] A) {
        ArrayList<Integer> result = new ArrayList<>();
        if (A == null || A.length == 0) {
            return result;
        }

        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < A.length; ++i) {
            int k = findAndInsert(list, A[i]);
            result.add(k);
        }

        return result;
    }


    private int findAndInsert(List<Integer> list, int target) {
        if (list.isEmpty()) {
            list.add(target);
            return 0;
        }

        int start = 0;
        int end = list.size()-1;
        while(start+1 < end) {
            int middle = start + (end-start)/2;
            if(list.get(middle) < target) {
                start = middle;
            } else {
                end = middle;
            }
        }

        if (list.get(start) >= target) {
            list.add(start, target);
            return start;
        } else if (list.get(end) < target) {
            list.add(target);
            return end+1;
        }

        list.add(end, target);
        return end;
    }