# 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

1. an iteration
2. and a two_Sum problem.
3. break two_Sum problem to
1. a loop
2. 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) -> List[List[int]]:
"""
:type nums: List[int]
:type target: int
"""
nums.sort() #sort for skip duplicate and binary search

if len(nums) < 3:
return []

i = 0
while i < len(nums) - 2:
complement = target - nums[i]

self.two_sum(nums[i+1:], complement)
i += 1 #increment the index
while i < 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) < 2:
return []

i = 0
while i < 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 < len(nums) and nums[i] == nums[i-1]:
i += 1

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

if find > L[mid]:
upper_half = L[mid+1:]
return self.bi_search(upper_half, find)
if find < 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?

• Binary search is good at O(log n), but hash search is better at O(1). Commented Mar 23, 2019 at 0:40

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) < 1:, use a while len(L) > 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.