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]

Solution

class Solution:
    """
    @param A: A list of integer
    @return: The number of element in the array that 
             are smaller that the given integer
    """
    def countOfSmallerNumber(self, A, queries):
        A = sorted(A)

        results = []
        for q in queries:
            results.append(self.countSmaller(A, q))
        return results

    def countSmaller(self, A, q):
        # find the first number in A >= q
        if len(A) == 0 or A[-1] < q:
            return len(A)

        start, end = 0, len(A) - 1
        while start + 1 < end:
            mid = (start + end) / 2
            if A[mid] < q:
                start = mid
            else:
                end = mid
        if A[start] >= q:
            return start
        if A[end] >= q:
            return end
        return end + 1