Another Binary Search idea


  • 2
    Y

    This idea is to use alternative binary search rather than simply search the target - number[i] each time.
    Although the worst case will also result in O(n) time complexity, but the overall performance is much better if the input is very sparse.

    var twoSum = function(numbers, target) {
    
        var i=0, j=numbers.length-1;
        var sum;
        
        while (i<j){
            //move j using binary search to find largest nums[j] that nums[i] + nums[j] <= target   
            var tmpi = i+1, tmpj = j;
            var first = numbers[i];
            while (tmpi <= tmpj){
                var m = Math.floor((tmpi+tmpj)/2);
                if (numbers[m] + first === target){
                    return [i+1, m+1];
                }
                else if (numbers[m] + first > target){
                    tmpj = m-1;
                }
                else {
                    tmpi = m+1;
                }
            }
            j = tmpj;
            
            //move i using binary search to find smallest nums[i] that nums[i] + nums[j] >= target   
            var last = numbers[j];
            tmpi = i+1, tmpj = j-1;
            while (tmpi <= tmpj){
                var m = Math.floor((tmpi+tmpj)/2);
                if (numbers[m] + last === target){
                    return [m+1, j+1];
                }
                else if (numbers[m] + last > target){
                    tmpj = m-1;
                }
                else {
                    tmpi = m+1;
                }
            }
            i = tmpi;
        }
    };

  • 0
    A

    Would you mind explain why worse case O(n)? I have the same idea, but don't know what the time complexity is... Thanks.


  • 0
    Y

    Please consider this case: 1, 3, 5, 7, 9, 11, 13 .... n+1, n+2, n+3, n+5, ... 2n-1, 2n+1 and your target is 2n+3, it will cost you O(n) binary search to reach the middle for n+1 and n+2


  • 0
    A

    Ah! I see, thanks for your explanation.


  • 0
    K

    I have the same idea, but I think the worse case is O(nlogn) because we need n times binary search and each time the range is only subtract by one.


Log in to reply
 

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