Binary Search Approach (https://leetcode.com/problems/two-sum)

two-sum.cpp

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<pair<int, int>> numsNpos;
        
        for (auto i = 0; i < nums.size(); i++) {
            numsNpos.push_back({ nums[i], i });
        }
        sort(numsNpos.begin(), numsNpos.end());
        
        for (auto i = numsNpos.begin(); i != numsNpos.end(); ++i) {
            auto k = target - (*i).first;
            pair<int, int> t = {k, 0};
            auto j = lower_bound(i + 1, numsNpos.end(), t);

            if (j != numsNpos.end() && k == (*j).first) {
                return {(*i).second, (*j).second};
            }
        }
        assert(false);
    }
};