Real Binary Search Approach with One Loop


  • 0
    X

    Some existing posts only used binary search for one value, and their algorithm could be described as following:

    for(i = 0; i < nums; i++)
       num1 = nums[i]; 
       num2 = target - num1;
       binary search num2 in nums[i:], if found, return the index of num1, num2
    

    Their approach actually takes O(nlogn) time. The worst case is num1 and num2 is the center. It takes log(n-1)+log(n-2)+..log(n/2) ~ nlogn

    My idea only used one loop. The worst case is:

    • the input arry contains same values, or
    • num1 and num2 is in the center
      so every time we move the cursor by 1, which takes O(n).In other cases my approach is faster than linear scan.

    We could start with left = 0, right = nums.size()-1, and mid = (left+right)/2.
    Since the input vector is sorted, we know nums[left] < nums[mid] < nums[right], so that: nums[left] + nums[mid] < nums[left] + nums[right] < nums[mid] + nums[right].

    If nums[left] + nums[mid] > target, the 2 number we are looking for must be within nums[left:mid-1]. Similarly, if nums[right] + nums[mid] < target, the 2 number we are looking for must be within nums[mid+1:right].

    Following is an accepted C++ implemetaion.

    class Solution {
    public:
       vector<int> twoSum(vector<int>& numbers, int target) {
           int left = 0, right = numbers.size()-1; 
           vector<int> ret; 
           while (left < right){
               int mid = left + (right-left)/2; 
               int sum = numbers[left] + numbers[right]; 
               if (sum == target){
                   ret.push_back(left+1); 
                   ret.push_back(right+1); 
                   break; 
               }
               else if (sum < target){
                   left = (numbers[mid] + numbers[right] < target)?mid:left+1;
               }else{
                   right = (numbers[mid] + numbers[left] > target)?mid:right-1;
               }
              
           }
           return ret; 
       }
    };
    

Log in to reply
 

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