A O(logN) solution with easy understanding explaination

• There is a normal way to find answer like this:

``````public int[] TwoSum(int[] numbers, int target)
{
int low = 0;
int up = numbers.Count() - 1;
int sum;
while (low < up)
{
sum = numbers[low] + numbers[up];
if (sum > target)
up--;
else if (sum < target)
low++;
else
break;
}
return new int[] { low + 1, up + 1 };
}
``````

This is O(N) solution.
If the final value of low is very close to 0 and the final value of up is very close to N-1, it will work very fast.
But if not , it will wast a lot of time to up-- and low++.
Because the array is already sorted, we can use binary search to speed up this process.
If sum > target, we find next up which makes numbers[low]+numbers[up-1]<target<=numbers[low]+numbers[up].
If sum < target, we find next low which makes numbers[low]+numbers[up]<=target<numbers[low+1]+numbers[up].
If sum = target, we get the answer.
Here is my code:

``````static int[] TwoSum(int[] numbers, int target)
{
int low = 0;
int up = numbers.Count() - 1;
int sum;
while (low < up)
{
sum = numbers[low] + numbers[up];
if (sum > target)
{
up = Array.BinarySearch(numbers, low, up - low + 1, target - numbers[low]);
if (up < 0) up = ~up;
if (numbers[low] + numbers[up] != target) up--;
}
else if (sum < target)
{
low = Array.BinarySearch(numbers, low, up - low + 1, target - numbers[up]);
if (low < 0) low = ~low;
}
else
break;
}
return new int[] { low + 1, up + 1 };
}
``````

By the way, Array.BinarySearch is a method of Array class in .Net, you can find help at: https://msdn.microsoft.com/en-us/library/windows/apps/y15ef976(v=vs.105).aspx

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