# C++ O(logn)~O(n) : An combination of binary-search and two-pointers

• ``````class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
// Current Version : Time -> O(logn) ~ O(n), space -> O(1)
int start = 0, end = numbers.size() - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (numbers[mid] + numbers[start] == target) {
return {start+1, mid+1};
} else if (numbers[mid] + numbers[end] == target) {
return {mid+1, end+1};
} else if (numbers[mid] + numbers[start] > target) {
end = mid;
} else if (numbers[mid] + numbers[end] < target) {
start = mid;
} else {
if (numbers[start] + numbers[end] == target) {
return {start+1, end+1};
} else if (numbers[start] + numbers[end] < target) {
start = start + 1;
} else {
end = end - 1;
}
}
}
return {start+1, end+1};

// Expected Version: Time -> O(logn)？

/* Other Version:
1. Binary Search:
Solution -> i from 1 -> n, binary search target - numbers[i]
time -> O(nlogn), space -> O(1)
2. Two Pointers:
Solution -> start = 0, end = n - 1
start + end < target start++
start + end > target end--
time -> O(n), space -> O(1)
*/
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.