Count of Smaller Number

Give you an integer array (index from 0 to n-1, where n is the size of this array, value from 0 to 10000) and an query list. For each query, give you an integer, return the number of element in the array that are smaller than the given integer.

Example

For array [1,2,7,8,5], and queries [1,8,5], return [0,4,2]

Notes:

1. Binary Search, sort the array and binary search loop
2. Segment tree

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

        Arrays.sort(A);

        for (int i = 0; i < queries.length; ++i) {
            int k = findFirstLargerPosition(A, queries[i]);
            result.add(k);
        }

        return result;
    }

    private int findFirstLargerPosition(int[] A, int target) {
        if (A == null || A.length == 0) {
            return 0;
        }

        int start = 0;
        int end = A.length-1;

        while(start+1 < end) {
            int middle = start + (end-start)/2;
            if (A[middle] < target) {
                start = middle;
            } else {
                end = middle;
            }
        }

        if (A[start] >= target) {
            return start;
        }

        return end;
    }