Binary Search Off By 1 Infinite Loop-CodePudding

So I have the following binary search algorithm that sometimes runs into an infinite loop:

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        i, j = 0, len(nums)-1
        mid = (j i)//2
        while i<j: 
            if nums[mid] == target:
                return mid
            if nums[mid] > target: 
                j = mid
                mid = (j i)//2
            else: 
                i = mid
                mid = (j i)//2                
        
        return mid if nums[mid] == target else -1

The correct version has that j = mid 1 and i = mid-1. In certain cases, the code above will run into an infinite loop if the mid pointer is not with in the interval bounded by i and j. Why does that happen, and more importantly, why does having the different assignments prevent that?

An example test case is:

nums = [-1,0,3,5,9,12], target = 2

CodePudding user response：

The rule for making a binary search that doesn't produce an infinite loop is to make sure that every case always narrows the search space. Since you've already checked mid, you can set your bounds so that it isn't included in the range any more. You can also simplify your code to calculate mid at the top of the loop so you're not doing it redundantly for every case.

    def search(self, nums: List[int], target: int) -> int:
        i, j = 0, len(nums)-1
        while i<j:
            mid = (j i)//2
            if nums[mid] == target:
                return mid
            if nums[mid] > target: 
                j = mid - 1
            else: 
                i = mid   1
        
        return i if nums[i] == target else -1

CodePudding user response：

Using your sample test case, the 2nd iteration gives:

i = 0, j = 2, and mid = 1

then at the 3rd iteration, it gives:

i = 1, j = 2, and mid = 1

If you track it further, mid = 1 will be the repeating result as i is always 1 and j is always 2. This is the cause of the infinite loop.

Here is a refactored version that captures your provided edge case:

nums = [-1, 0, 3, 5, 9, 12]
target = 2


def search(nums: List[int], target: int) -> int:
    i, j = 0, len(nums)-1
    mid = (j i)//2
    while i < j:
        print(i, j, mid)
        if nums[mid] == target:
            return mid
        if nums[mid] > target:
            j = mid
            mid = (j i)//2
        elif nums[mid] < target and nums[mid 1] < target:
            i = mid
            mid = (j i)//2
        else:
            return -1

    return mid if nums[mid] == target else -1

I would refactor it further to become more simple and readable:

def search(nums: List[int], target: int) -> int:
    i, j = 0, len(nums)-1
    while i < j:
        mid = (i j)//2
        if nums[mid] < target:
            i = mid 1
        elif nums[mid] > target:
            j = mid-1
        else:
            return mid
    return -1

Explanation: if nums[mid]>target, we ignore right half and the vice versa. if our indexes have converged (i.e. i==j) and we still did not find the target, return -1