<commit_before>/* 
 * http://www.lintcode.com/en/problem/count-of-smaller-number/
 */

#include <iostream>
#include <vector>
using namespace std;

void printData(const vector<int> data) {
    for (int i = 0; i < data.size(); i++) {
        cout << data[i] << ", ";
    }
    cout << endl;
}


class Solution {
public:

    void swap(int& a, int& b) {
        int tmp = a;
        a = b;
        b = tmp;
    }


    void sort(vector<int> &data) {
        int size = data.size();
        for (int i = size; i >= 0; i--) {
            bool do_swap = false;
            for (int j = 0; j < i; j ++) {
                if (data[j] > data[j+1]) {
                    swap(data[j], data[j+1]);
                    do_swap = true;
                }
            }
            if (!do_swap) {
                break;
            }
        }
    }


    int countOfSmallerNumber(vector<int> &A, int query) {
        int i = 1;
        if (A.size() == 0 || A[0] >= query) {
            return 0;
        }
        for (; i < A.size(); i++) {
            if (A[i] >= query) {
                break;
            }
        }
        return i;
    }

    /**
     * @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) {
        sort(A);
        vector<int> result;
        for (int i = 0; i < queries.size(); i++) {
            result.push_back(countOfSmallerNumber(A, queries[i]));
        }
        return result;
    }
};

int main() {
    vector<int> data = {32, 67};
    vector<int> queries = {65, 50};

    Solution s;
    cout<< "sort result:" << endl;
    s.sort(data);
    printData(data);
    vector<int> result = s.countOfSmallerNumber(data, queries);

    cout<< "count result:" << endl;
    printData(result);
    return 0;
}<commit_msg>lintcode: count of all smaller number (second try)\n use dichotomy<commit_after>/* 
 * http://www.lintcode.com/en/problem/count-of-smaller-number/
 */

#include <iostream>
#include <vector>
using namespace std;

void printData(const vector<int> data) {
    for (int i = 0; i < data.size(); i++) {
        cout << data[i] << ", ";
    }
    cout << endl;
}


class Solution {
public:

    int countOfSmallerNumber(vector<int> &A, int query) {
        int start = 0, end = A.size();
        if (end == 0 || A[0] >= query) {
            return 0;
        }
        int mid;
        while (start < end - 1) {
            mid = (end + start) >> 1;
            if (query > A[mid - 1]) {
                start = mid;
            } else {
                end = mid;
            }
        }
        return start;
    }

    /**
     * @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) {
        sort(A.begin(), A.end());
        vector<int> result;
        for (int i = 0; i < queries.size(); i++) {
            result.push_back(countOfSmallerNumber(A, queries[i]));
        }
        return result;
    }
};

int main(int argc, char* argv[]) {
    vector<int> data = {1,2,4,6,7,8,10};
    vector<int> queries = {1, 5, 8};

    Solution s;
    vector<int> result = s.countOfSmallerNumber(data, queries);
    cout<< "count result:" << endl;
    printData(result);
    return 0;
}
{'fraction_non_alphanumeric': 0.15366705471478465, 'fraction_numerical': 0.011641443538998836, 'mean_word_length': 1.6830601092896176, 'pattern_counts': {'":': 0, '<': 57, '<?xml version=': 0, '>': 34, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1223617', 'n_tokens_mistral': 1176, 'n_tokens_neox': 1120, 'n_words': 305}