二分 P31

利用二分找到最后一个小于i的数的位置
在插入的时候要判断一下i与ans[l]的大小关系，如果i小于ans[l]，则需要将i插入到l前面，这种情况相当于没有找到小于i的位置

// Forward declaration of compare API.
// bool compare(int a, int b);
// return bool means whether a is less than b.

class Solution {
public:
    vector<int> specialSort(int N) {
        vector<int> ans;
        ans.push_back(1);
        for (int i = 2; i <= N; i++) {
            int l = 0, r = ans.size()-1;
            while (l < r) {
                int mid = (l + r + 1) >> 1;
                if (compare(ans[mid], i)) l = mid;
                else r = mid-1;
            }
            if (compare(i, ans[l])) ans.insert(ans.begin() + l, i);
            else 
            ans.insert(ans.begin() + l + 1, i);
        }
        return ans;
    }
};