3Sum Why this O(nlogn) solution doesn't work? I have been doing LeetCode and tackled the problem of the 3Sum and first I tried to do a O(nlogn) solution and after seeing the proposed solution I see that the solution is $O(n^2)$ or $O(n^2 \times \log n)$ and not only that but the problem is a highly researched topic so I don't think I found a better solution but can't see why my approach wouldn't work, can use help to figure it out.
The problem is the following
Find three numbers in an array such that $a + b + c = t$,
the LeetCode problem is slightly different in which you need to find the closest sum.
My code is the following:

Sort the array.
  Start with two pointers i=0 and j= last element of array
    Use binary search between i and j to find m such that arr[m] == target - arr[i] - arr[j], if such m doesn't exist return m such that arr[m] is the closest.
    If arr[i] + arr[m] + arr[j] == target then your finished.
    Otherwise if arr[i] + arr[m] + arr[j] &lt; target then add 1 to i else subtract 1 form j.
Repeat 3 → 5 until j - i == 2
Return the best found i,m,j

The logic in step 5 is that if the solution found is less than the target then we should increase i such that our next guess is bigger.
Code:
def binSearch(arr, s, e, t):
    m = (s + e) // 2
    r = m
    d = 9999
    while s &lt;= e:
        m = (s + e) // 2
        if arr[m] == t:
            return m
        elif arr[m] &gt; t:
            e = m - 1
        else:
            s = m + 1

        if d &gt; abs(t - arr[m]):
            d = abs(t - arr[m])
            r = m
    return r


class Solution:
    def threeSumClosest(self, nums, target: int) -&gt; int:
        nums.sort()

        s = 0
        e = len(nums) - 1
        minn = 999999
        t = ()
        while e - s &gt;= 2:
            left = nums[s]
            right = nums[e]
            remaining = target - (left + right)
            m = binSearch(nums, s + 1, e - 1, remaining)
            middle = nums[m]
            r = left + middle + right

            # print(&quot;i's: &quot;, (s,m,e))
            # print(&quot;values: &quot;, (nums[s], nums[m], nums[e]))
            # print(&quot;r&quot;, r)
            # print(&quot;**************&quot;)

            if r == target:
                return r
            elif r &lt; target:
                s += 1
            else:
                e -= 1

            if abs(target - r) &lt; minn:
                minn = abs(target - r)
                t = r
        return t
This fails for, e.g., [1, 9, 55, 55, 100], t=111. The first iteration finds 110 and increases i to exclude 1 as a possibility, but the only solution, [1, 55, 55], needs 1.
The basic problem is that when you increase i or reduce j, you are assuming that the element you just advanced past is not needed -- that there exists some solution that does not include it. But this is not justified by anything, and it could well be that all solutions need that element.
A great way to test algorithm ideas like this is to write a small program that generates many small random inputs, and compare the result of your algorithm on each of them to the result of a known-correct brute-force approach.