167. Two Sum II - Input array is sorted - 《Leetcode》

1. Use brute force:
2. Use binary search:

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/

1. Use brute force:

//12 ms    9.9 MB
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        vector<int> result;
        int l = 0, r = numbers.size() - 1;
        while(l < r && numbers[l] + numbers[r] != target){            
            if(numbers[l] + numbers[r] > target)
                r--;
            else if(numbers[l] + numbers[r] < target)
                l++;
        }
        result.push_back(l + 1);
        result.push_back(r + 1);
        return result;
    }
};

2. Use binary search:

//8 ms    9.6 MB
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        vector<int> result;
        int diff, second_l, second_r, median;
        for(int first = 0; first < numbers.size() - 1; first++) {
            diff = target - numbers[first];
            second_l = first + 1; 
            second_r = numbers.size() - 1;
            median = second_r;
            while(second_l < second_r){
                if(numbers[median] == diff){
                    break;
                }
                median = second_l + (second_r - second_l)/2;
                if(numbers[median] > diff)
                    second_r = median;
                else if(numbers[median] < diff)
                    second_l = median + 1;
            }
            if(numbers[median] == diff){
                return vector<int>{first+1, median+1};
            }
        }
        return {};
    }
};