Binary search when solution is at boundaries?

Question

When working with binary search algorithms, one updates one of the two pointers at each iteration. However, there are cases like the LeetCode problem where this would miss the solution.

For example, the following solution of threeSumClosest works

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        distance = float("inf")
        for idx, num in enumerate(nums):
            if num >= target:
                l = 0
                r = idx - 1
            else:
                l = idx + 1
                r = len(nums) -1
            while l < r:
                res = num + nums[l] + nums[r]
                if abs(target-res) < abs(distance):
                    distance = target - res
                if res < target:
                    l +=1
                else:
                    r -= 1
        return target - distance

However, computing mid and using l = mid + 1 or r = mid - 1 misses the solution. How do you handle these cases?

I was expecting that updating l or r to mid +1 or mid -1 the algorithm would find the right solution

Only one of them should have the ±1 adjustment. Breaking the symmetry will give you [half-open ranges](https://stackoverflow.com/questions/13066884/what-is-half-open-range-and-off-the-end-value), which are easier to work with. — John Kugelman, Jan 23 '23 at 03:35

score 0 · Answer 1 · answered Jan 23 '23 at 03:55

This question also appears in other forms, like finding the floor/ceiling of a number in a sorted list, or finding the insertion point of a number in a sorted list. In normal binary search if the middle element doesn’t match the predicate we look left or right, but in all of these problems we need to include it. For example, given list [1, 2, 4], find insertion point of 3.

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        lo = 0
        hi = len(nums) - 1

        while lo < hi:
            mid = lo + (hi - lo) // 2
            if nums[mid] == target:
                return mid
            if nums[mid] < target:
                lo = mid + 1
            else:
                hi = mid

        return lo + int(nums[lo] < target)

So we decide on one side to include it, but only on one side. Don't we risk infinite looping? — Wooden Marsupial, Jan 23 '23 at 16:53
@WoodenMarsupial the algorithm terminates properly. I recommend running the code shown against various input and try to understand what it does. — Abhijit Sarkar, Jan 23 '23 at 21:04

Binary search when solution is at boundaries?

1 Answers1