Two Sum II

Problem

Givens

  • Your returned answers (both index1 and index2) are not zero-based.
  • You may assume that each input would have exactly one solution and you may not use the same element twice.

Analysis

  • Array is sorted, so we can exploit the fact and stop when we reach a certain threshold.
  • When we see sorted array, binary searches can be a viable option.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
      /* if array is all positives then bin search */
      if (numbers[0] >= 0) {
        int low = 0;
        int high = numbers.size() - 1;

        while (low <= high) {
          int mid = (low + high) / 2;
          if (numbers[mid])
        }
      }
    }
};