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]

Note
We suggest you finish problem Segment Tree Build and Segment Tree Query II first.

Challenge
Could you use three ways to do it.

Just loop
Sort and binary search
Build Segment Tree and Search.

http://www.lintcode.com/en/problem/count-of-smaller-number/

Solution

BST解法如下：

class Solution {
public:
   /**
     * @param A: An integer array
     * @return: The number of element in the array that 
     *          are smaller that the given integer
     */
    vector<int> countOfSmallerNumber(vector<int> &A, vector<int> &queries) {
        vector<int> result;
        sort(A.begin(), A.end());
        for(auto const & val : queries) {
            result.emplace_back(FindCounterSmaller(A, val));
        }
        return result;
    }
    //find the number of elements in A < target
    //using binary search to find the first place where >= target
    int FindCounterSmaller(vector<int> & A, int target) {
        if(A.empty()) return 0;
        int start = 0;
        int end = A.size()-1;
        while(start + 1 < end) {
            int mid = start + (end - start) /2;
            if(A[mid] < target) { //target is on the right of mid
                start = mid;
            } else { //A[mid] > target || target == A[mid], move to left
                end = mid;
            }
        }
        if(A[end] < target) {
            return end +1;
        }
        if(A[start] < target) {
            return start+1;
        } 
        return 0;
    }
};