Bit late to the party :), but here goes anyway: the standard O(N) solution uses left++ and right-- to move the pointers to the desired solution. This can be made more efficient, in O(log(N)) as mentioned, by not moving the pointers one step at a time, but many steps at a time using binary search.
Essentially what the functions largestSmallerOrLastEqual() and its counterpart do is instead of doing left++ until the sum gets too high, instead do a binary search for the first position for which this holds true also.
Suppose we take the input [1, 2, 3, ... , 1_000_000], i.e, the first million numbers, with target 1_999_999. The solution for that is the last two positions, because 999_999 + 1_000_000 = 1_999_999.
In the O(N) solution this would mean doing left++ 999_998 times! Instead, smallestLargerOrFirstEqual() does a binary search for target - numbers[start] = 1_000_000 - 1 = 999_999, and finds this in only about 20 steps!
(It also takes into account that the target may not be found, in case it selects the value next to it.)
In situation 2, if numbers[i] + numbers[j] < target, because the array is sorted, we know that numbers[j*] > numbers[j], and j* > j. So we should check the index bigger than j.
Great explanation! I was able to understand how to use two pointers to reduce time complexity. Thank You!
Your solution does not work with negative ints in the input. I do not believe you can use a binary search on this problem unless you are told there will only be positives (which we have not been given in the instructions)