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


  • 0
    R

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

  • 0
    • 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).

  • 0
    R

    @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 };
            }
        }

Log in to reply
 

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