# My C++ solution using binary search. O(nlgn)~O(n^2*lgn)

• I add binary search to replace the j++ / k--
And the time cost reduced from 9ms to 6ms, according to the inaccurate evaluation of leetcode

In best situation , time cost can be O(nlgn)

For example,
[1,2,...,100]
1000

However, in worst situation, time cost maybe reach O(n^2*lgn)
Though I can't find exactly such a case, this case may be close:
[0,1,3,5,...49,51,52,54,...100]
102

when i==0, the while loop of j and k costs nlgn

All in all, I think the binary search does more good than harm.

``````    // find the last element equal to or smaller than the key, in the range left to right
inline int findLastEqualSmaller(const vector<int> &array, int key, int left, int right) {
// must use <=
while (left <= right) {
int mid = (left + right) / 2;
if (array[mid] > key) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return right;
}

// find the first element equal or larger than the key, int the range left to right
inline int findFirstEqualLarger(const vector<int> &array, int key, int left, int right) {
// must use <=
while (left <= right) {
int mid = (left + right) / 2;
if (array[mid] >= key) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return left;
}

int threeSumClosest(vector<int> &nums, int target) {
int min = INT_MAX, ans = 0, temp;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size() - 2; i++) {
int j = i + 1, k = nums.size() - 1, sum = target - nums[i];
while (j < k) {
temp = sum - nums[j] - nums[k];
if (abs(temp) < min) {
min = abs(temp);
ans = target - temp;
if (min == 0) return ans;
}
if (nums[j] + nums[k] < sum) {
temp = findLastEqualSmaller(nums, sum - nums[k], j + 1, k - 1);
j == temp ? j++ : j = temp;
} else {
temp = findFirstEqualLarger(nums, sum - nums[j], j + 1, k - 1);
k == temp ? k-- : k = temp;
}
}
}
return ans;
}
``````

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