I independently developed a C++ solution sharing almost exactly the same idea as this Java solution https://leetcode.com/discuss/72232/a-o-nlgn-solution

The idea is to sort the array first, maintaining two elements: left and right, and then to use binary search to look for the middle element, gradually moving left or right element to shrink the search range.

However, look at the following simple example,

[-5, -5, -4, 0, 0, 3, 3, 4, 5] and search for -2.

It is not hard to see that we can actually obtain the exact match by picking -5, 3 and 0.

We first fix -5 and 5 and then look for -2.

The thing is that -4 and 0 can both reach the smallest gap, so we have an ambiguity of either moving the left or right element, which makes the correctness based on the input data.

If we choose -4 as the current middle element, then we have to move the left element.

After two iterations, both -5 are moved out of the checking range, and we can not get the correct answer.

The aforementioned Java implementation seems to be correct on this particular example, because it returns 0 as the mid element.

But again this solution seems to be dependent on input data.

If I understand correctly, all O(nlogn) and O(n^2) solutions are based on moving the left or right element, although I cannot prove it, I have a feeling that they might all share the same ambiguity.

I hope I missed something tiny but important.

Any one would like to comment on this?

The code is attached as follows:

```
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
if (nums.size() < 3) return 0;
sort(nums);
int left = 0; int right = nums.size()-1;
int gap = INT_MAX;
int sum3 = 0;
while (left <= right-2) {
int sum2 = nums[left] + nums[right];
int third = target - sum2;
if (binary_search(nums.begin()+left+1, nums.begin()+right, third)) {
return target;
}
// "low" is the place where the desired mid value should be
// upper_bound() and lower_bound() should return the same place because there is no exact match
// otherwise, binary_search() would have returned already
auto low = lower_bound(nums.begin()+left+1, nums.begin()+right, third);
if (low != nums.begin()+right) {
int newgap = abs(sum2+*low-target);
if (gap > newgap) {
gap = newgap;
sum3 = sum2 + *low;
}
}
if (low != nums.begin()+left+1) {
int newgap = abs(sum2+*(low-1)-target);
if (gap > newgap) {
gap = newgap;
sum3 = sum2 + *(low-1);
}
}
if (sum3 > target)
--right;
else
++left;
}
return sum3;
}
};
```