The idea is:

- Have a left and right pointer, which are initialized at both ends of the array
- If the sum of the values pointed by these two pointers is larger than the target, keep the left pointer constant, and binary search from right, such that:
- If you can find the complement value (target - nums[left]), return it.
- Else return the greatest value that is smaller than the target, so that we can continue searching from left in the next iteration

- Similarly, if the sum is smaller than the target, keep the right pointer constant, and binary search from left, such that:
- If you can find the complement value (target - nums[right]), return it.
- Else return the smallest value that is greater than the target, so that we can continue searching from right in the next iteration.

**Edit**: Fixed a couple bugs based on StefanPochmann's feedback, reconsidered the complexity and ran a detailed perf analysis to understand better, which you can find in my next post below.

```
public class Solution
{
public int[] TwoSum(int[] numbers, int target)
{
int[] res = new int[2];
int left = 0;
int right = numbers.Length - 1;
int sum = numbers[left] + numbers[right];
while (sum != target)
{
int comp;
if (sum < target)
{
// Keep right constant, search from left
comp = target - numbers[right];
left = Search(numbers, left, right - 1, comp, false);
}
else
{
// Keep left constant, search from right
comp = target - numbers[left];
right = Search(numbers, left + 1, right, comp, true);
}
sum = numbers[left] + numbers[right];
}
res[0] = left + 1;
res[1] = right + 1;
return res;
}
private int Search(int[] arr, int low, int high, int target, bool searchFromRight)
{
if (low > high)
throw new Exception("No Solution");
int mididx = (low + high) / 2;
int midnum = arr[mididx];
if (midnum == target)
return mididx;
if (searchFromRight)
{
// Find target, or the greatest number smaller than target
if (midnum < target)
{
if (mididx == high || arr[mididx + 1] > target)
return mididx;
return Search(arr, mididx + 1, high, target, searchFromRight);
}
return Search(arr, low, mididx - 1, target, searchFromRight);
}
// Find target, or the smallest number greater than target
if (midnum > target)
{
if (mididx == low || arr[mididx - 1] < target)
return mididx;
return Search(arr, low, mididx - 1, target, searchFromRight);
}
return Search(arr, mididx + 1, high, target, searchFromRight);
}
}
```