Clean 0ms Binary Search Solution (beats 99.22%)


  • 0
    W
    class Solution {
        public int[] twoSum(int[] nums, int target) {
            
            int li = 0;
            int ri = nums.length - 1;
            while(li < ri) {
                int sum = nums[li] + nums[ri];
                if(sum < target) {
                    li = largestIndexSmallerThanOrEqual(nums, li, ri, target);
                } else if(sum > target) {
                    ri = smallestIndexLargerThanOrEqual(nums, li, ri, target);
                } else {
                    return new int[]{li+1, ri+1};
                } 
            }
            return null;
        }
        
        public int largestIndexSmallerThanOrEqual(int[] nums, int origLi, int origRi, int target) {
            
            int li = origLi + 1;
            int ri = origRi - 1;
            
            while(li <= ri) {
                int mi = li + (ri - li)/2;
                if(nums[mi] + nums[origRi] <= target) {
                    if(mi == ri || nums[mi+1] + nums[origRi] > target) {
                        return mi;
                    } else {
                        li = mi + 1;
                    }
                } else {
                    ri = mi - 1;
                }
            }
            return origLi + 1;
        }
        
        public int smallestIndexLargerThanOrEqual(int[] nums, int origLi, int origRi, int target) {
            
            int li = origLi + 1;
            int ri = origRi - 1;
            
            while(li <= ri) {
                int mi = li + (ri - li)/2;
                if(nums[origLi] + nums[mi] >= target) {
                    if(mi == li || nums[origLi] + nums[mi-1] < target) {
                        return mi;
                    } else {
                        ri = mi - 1;
                    }
                } else {
                    li = mi + 1;
                }
            }
            return origRi - 1;
        }
    }
    

Log in to reply
 

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