Solution for TwoSum from leetcode

001-TwoSum.cpp

class Solution {
public:
    vector<int> twoSum(vector<int> &numbers, int target) {
        vector<int> ans(2);
        // Remember indexes
        vector<int> sorted(numbers);

        // Merge Sort [O(nlog(n))]
        mergeSort(sorted);
        for (int i = 0; i < numbers.size(); i++) {
            // Binary search for the missing term
            int j = binarySearch(sorted, target - sorted[i]);
            if (j != -1) {
                // Search for the original index
                int k = 0;
                for (int n = 0; n < numbers.size(); n++) {
                    if (numbers[n] == sorted[i]) {
                        ans[k] = n+1;
                        k++;
                    } else if (numbers[n] == sorted[j]) {
                        ans[k] = n+1;
                        k++;
                    }
                }
                // Sort answer
                if (ans[0] > ans[1]) {
                    int tmp = ans[0];
                    ans[0] = ans[1];
                    ans[1] = tmp;
                }
                return ans;
            }
        }
        // Something gone wrong
        return ans;
    }

private:
    int binarySearch(vector<int> &numbers, int target) {
        int max = numbers.size() - 1;
        int min = 0;

        while (max >= min) {
            int mid = (max - min)/2 + min;
            if (numbers[mid] == target) {
                return mid;
            } else if (numbers[mid] < target) {
                min = mid + 1;
            } else {
                max = mid - 1;
            }
        }
        return -1;
    }

    void mergeSort(vector<int> &numbers) {
        if (numbers.size() == 1) {
            return;
        }

        int mid = numbers.size()/2;
        vector<int> right(mid);
        vector<int> left(numbers.size() - mid);

        for (int i = 0; i < right.size(); i++) {
            right[i] = numbers[i];
        }

        for (int i = 0; i < left.size(); i++) {
            left[i] = numbers[i+mid];
        }

        mergeSort(right);
        mergeSort(left);

        int rightCnt = 0;
        int leftCnt = 0;
        for (int i = 0; i < numbers.size(); i++) {
            if (rightCnt < right.size()) {
                if (leftCnt < left.size()) {
                    if (left[leftCnt] < right[rightCnt]) {
                        numbers[i] = left[leftCnt];
                        leftCnt++;
                    } else {
                        numbers[i] = right[rightCnt];
                        rightCnt++;
                    }
                } else {
                    numbers[i] = right[rightCnt];
                    rightCnt++;
                }
            } else {
                numbers[i] = left[leftCnt];
                leftCnt++;
            }
        }
    }
};