# C++ O(n log n) using sort and binary search

1. sort nums
2. find smallest 3Sum greater than target
3. find largest 3Sum less than target
4. compare answers from steps 2 and 3, return the better one.
``````class Solution {
public:
int bin_search(vector<int>& nums, int lb, int ub, int target){
int mid;
while(lb <= ub){
mid = (lb + ub) / 2;
if(nums[mid] == target){
return mid;
}
else if(nums[mid] < target){
lb = mid + 1;
}
else if(nums[mid] > target){
ub = mid - 1;
}
else
throw -1;
}
return ub;
}
int closest_less_than_target(vector<int>& nums, int target){
int i=0, j=nums.size() - 1;
int min_poss_sum;
int ans = accumulate(nums.begin(), nums.begin() + 3, 0);
while(i < j){
min_poss_sum = 2 * nums[i] + nums[j];
if(min_poss_sum > target){
j--;
}
else{
int ind = bin_search(nums, i+1, j-1, target - nums[i] - nums[j]);
if(ind > i){
int cand = nums[ind] + nums[i] + nums[j];
if(abs(target - cand) < abs(target - ans))
ans = cand;
}
i++;
}
}
return ans;
}

int closest_greater_than_target(vector<int>& nums, int target){
int i=0, j=nums.size() - 1;
int max_poss_sum;
int ans = accumulate(nums.end() - 3, nums.end(), 0);
while(i < j){
max_poss_sum = nums[i] + 2 * nums[j];
if(max_poss_sum < target){
i++;
}
else{
int bs_target = target - nums[i] - nums[j];
int ind = bin_search(nums, i+1, j-1, bs_target);
if(ind <= i)
ind += 1;

if(ind > i && ind < j){
int cand = nums[ind] + nums[i] + nums[j];
if(abs(target - cand) < abs(target - ans))
ans = cand;
}
j--;
}
}
return ans;
}

int threeSumClosest(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
int ans1 = closest_greater_than_target(nums, target);
int ans2 = closest_less_than_target(nums, target);
if(abs(ans1 - target) < abs(ans2 - target))
return ans1;
else
return ans2;
}
};
``````

• The sort itself is O(n^2).

• @leaper
I believe C++ sort uses Introsort, which is a variant of Quicksort that changes to Heapsort when recursion depth reaches a certain level, and has a worst case complexity of O(n log n).

• complexity

Thanks! Learned more :)

• @atruecubsfan Your algorithm is wrong.
leetcode default testcase suite doesn't cover corner cases, so you got a FAKE acceptance.
Try the following testcase:

[-5,-4,-1,1,1,5,8]
0

-1