# Binary Search Solution Idea - Programmatic Performance Comparison With the Linear Method

• 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);
}
}
``````

• Fails the provided Custom Testcase `[2,3,4], 6`, returning `[0, 2]` instead of `[1, 3]`.
• The case it fails when submitted has array length 65, that's not "large" but small.
• The way to prevent the SO in that case is to fix your incorrect Search function (just make it print its parameters and you'll see it's doing something wrong).
• The method is neither O(log N) average nor O(n).

• @StefanPochmann Thanks for the comments.
I found two bugs in the code which caused the failures and the stack overflow, and fixed them both. It gets Accepted now. I have updated the code.

I agree that the complexity analysis isn't straightforward. In the worst case it will end up in O(NlogN) complexity. But in average case I think it's slightly better than O(N)
In order to verify this, I did the below test:

• Method-1: standard O(N) two pointer method approaching from both sides.

• Method-2: My binary search method above.

• Experiment: Run both methods for 1000 times, with input arrays of size 1000 whose content and the target are generated randomly in each iteration.
• Result: Binary search is about 10% faster than the linear solution, but the difference also changes if you play with the array size.

Here's the test code (the linear method's code is below the test code):

``````            DateTime starttime = DateTime.Now;
Random rand = new Random();
int arrSize = 1000;
int iterationCount = 1000;

for (int it = 0; it < iterationCount; ++it)
{
int[] arr = new int[arrSize];
for (int i = 0; i < arrSize; ++i)
{
arr[i] = rand.Next(arrSize);
}

Array.Sort(arr);

int first = rand.Next(arrSize);
int second = rand.Next(arrSize);
while (second == first)
second = rand.Next(arrSize);

int target = arr[first] + arr[second];

TwoSum2Linear ts = new TwoSum2Linear();
int[] res = ts.TwoSum(arr, target);
}

DateTime endtime = DateTime.Now;
Console.WriteLine("Elapsed time for " + iterationCount + " iterations of Linear Search: " + endtime.Subtract(starttime).TotalMilliseconds + " ms" + Environment.NewLine);

starttime = DateTime.Now;
for (int it = 0; it < iterationCount; ++it)
{
int[] arr = new int[arrSize];
for (int i = 0; i < arrSize; ++i)
{
arr[i] = rand.Next(arrSize);
}

Array.Sort(arr);

int first = rand.Next(arrSize);
int second = rand.Next(arrSize);
while(second == first)
second = rand.Next(arrSize);

int target = arr[first] + arr[second];

TwoSum2 ts = new TwoSum2();
int[] res = ts.TwoSum(arr, target);
}

endtime = DateTime.Now;
Console.WriteLine("Elapsed time for " + iterationCount + " iterations of Binary Search: " + endtime.Subtract(starttime).TotalMilliseconds + " ms" + Environment.NewLine);
``````

Linear Search Method:

``````    public class TwoSum2Linear
{
public int[] TwoSum(int[] arr, int target)
{
int left = 0;
int right = arr.Length - 1;

int sum = arr[left] + arr[right];

while (sum != target)
{
if (sum < target)
{
sum = arr[++left] + arr[right];
}
else
{
sum = arr[left] + arr[--right];
}
}

return new int[] { left + 1, right + 1 };
}
}``````

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