A binary search solution to 3Sum I tried a binary solution to 3Sum problem in LeetCode:


  Given an array nums of \$n\$ integers, are there elements \$a\$, \$b\$, \$c\$ in nums such that \$a + b + c = 0\$? Find all unique triplets in the array which gives the sum of zero.
  
  Note:
  
  The solution set must not contain duplicate triplets.
  
  Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]



Ｍy plan: divide and conquer threeSum to


an iteration   
and a two_Sum problem.  
break two_Sum problem to   


a loop 
binary search 



The complexity is: \$O(n^2\log{n})\$.

 class Solution:
    """
    Solve the problem by three module funtion
    threeSum
    two_sum
    bi_search 
    """
    def __init__(self):
        self.triplets: List[List[int]] = []

    def threeSum(self, nums, target=0) -&gt; List[List[int]]:
        """
        :type nums: List[int]
        :type target: int 
        """
        nums.sort() #sort for skip duplicate and binary search 

        if len(nums) &lt; 3:
            return []

        i = 0
        while i &lt; len(nums) - 2:
            complement = target - nums[i]

            self.two_sum(nums[i+1:], complement)
            i += 1 #increment the index 
            while i &lt; len(nums) -2 and nums[i] == nums[i-1]: #skip the duplicates, pass unique complement to next level.
                i += 1 

        return self.triplets


    def two_sum(self, nums, target):
        """
        :type nums: List[int]
        :tppe target: int
        :rtype: List[List[int]]
        """
        # nums = sorted(nums) #temporarily for testing.
        if len(nums) &lt; 2:
            return [] 

        i = 0
        while i &lt; len(nums) -1:
            complement = target - nums[i]

            if self.bi_search(nums[i+1:], complement) != None:

                # 0 - target = threeSum's fixer 
                self.triplets.append([0-target, nums[i], complement]) 
            i += 1

            while i &lt; len(nums) and nums[i] == nums[i-1]:
                i += 1 

    def bi_search(self, L, find) -&gt; int:
        """
        :type L: List[int]
        :type find: int 
        """
        if len(L) &lt; 1: #terninating case 
            return None 
        else:
            mid = len(L) // 2
            if find == L[mid]:
                return find 

            if find &gt; L[mid]:
                upper_half = L[mid+1:]
                return self.bi_search(upper_half, find)
            if find &lt; L[mid]:
                lower_half = L[:mid] #mid not mid-1
                return self.bi_search(lower_half, find)


I ran it but get the report


  Status: Time Limit Exceeded


Could you please give any hints to refactor?

Is binary search is an appropriate strategy?
Your bi_search() method is recursive.  It doesn’t have to be.  Python does not do tail-call-optimization: it won’t automatically turn the recursion into a loop.  Instead of if len(L) &lt; 1:, use a while len(L) &gt; 0: loop, and assign to (eg, L = L[:mid]) instead of doing a recursive call. 

Better: don’t modify L at all, which involves copying a list of many numbers multiple times, a time consuming operation.  Instead, maintain a lo and hi index, and just update the indexes as you search. 

Even better: use a built in binary search from import bisect.