Binary Search Off By 1 Infinite Loop

Question

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

Answer 1

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