167_two_sum_ii_input_array_is_sorted_SUBOPTIMAL.cc

#include <vector>
 
// This is a suboptimal solution. It uses Two Pointers + Binary Search
 
class Solution {
public:
    int binarySearch(std::vector<int>& v, int t, int ignore) {
        int l = 0;
        int h = v.size() - 1;
 
        while (l <= h) {
            int m = l + (h - l) / 2;
            if ((v[m] == t) && (m != ignore)) return m;
            if ((v[m] < t) && (m != ignore)) l = m + 1;
            else h = m - 1;
        }
 
        return -1;
    }
 
    std::vector<int> twoSum(std::vector<int>& numbers, int target) {
        if (numbers.size() == 2) return std::vector<int>{1, 2};
 
        int slow = 0, fast = numbers.size() / 2;
        std::vector<int> result;
 
        for (int i = 0; i < numbers.size(); i++) {
            int idx = binarySearch(numbers, target - numbers[i], i);
            if (idx == -1) continue;
 
            if (i < idx) {
                result.push_back(++i);
                result.push_back(++idx);
                break;
            }
 
            result.push_back(++idx);
            result.push_back(++i);
            break;
        }
 
        return result;
    }
};