> For the complete documentation index, see [llms.txt](https://liuxue2010.gitbook.io/data-structure-and-algorithms/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://liuxue2010.gitbook.io/data-structure-and-algorithms/binary-search/count-of-smaller-number.md).

# 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
```