Index Out of Range In A Recursive Call (Binary Search)

Question

I have been trying to solve this leetcode problem. The problem is to find range of a target value in a non-decreasing list. I am searching for a target value in a list using binary search, then 'ripling' out of that index as I exit the recursive call to see if here are any repeatted instances of that target and returning the range. My problem is the leetcode compiler is giving me a really bizzare index out of range error when I try to run the code. Here is my code:

class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """

        # Recursive Count (counts the number of recursive exits)
        RC = [0]
        length = len(nums) -1

        def getRange(left, right, nums):
            if(left == right):
                # Base case reached
                return [left, right]

            mid = (left + right) // 2
            indices = []

            # Searching for the middlle target index
            if (nums[mid] == target):
                indices = getRange(mid, mid, nums)
            elif (nums[mid] < target):
                indices = getRange(mid + 1, right, nums)
            elif (nums[mid] > target):
                indices = getRange(left, mid - 1, nums)
            
            # Ripling (as the program exits the last recursive call)
            if  indices[0] != 0 and nums[indices[0]] - RC[0] == target:
                indices[0] = indices[0] - 1
            elif indices[1] != length and nums[indices[1]] + RC[0] == target:
                indices[1] = indices[1] + 1

            RC[0] = RC[0] + 1
            return indices

        return getRange(0, length, nums)

And here is the error:

IndexError: list index out of range
    if (nums[mid] == target):
Line 22 in getRange (Solution.py)
    return getRange(0, length, nums)
Line 38 in searchRange (Solution.py)
    ret = Solution().searchRange(param_1, param_2)
Line 66 in _driver (Solution.py)
    _driver()
Line 76 in <module> (Solution.py)

It highlights line 22 as the problem. That is this line:

if (nums[mid] == target):

I don't understand why nums[mid] is out of range. The calculation for mid is a simple (left + right)/2, so for a list in non-decreasing order it should be imppossible for mid to go out of range. I have traced the iterations carefully with leetcode's input values and the program behaves exactly as I expect it to on paper.

At first I used the global variable for nums, and I thought that maybe the compiler was creating a new subsection of the nums array for every recursive call of the binary search algorithm, so I passed the original nums array into each recursive call. Unfortunately that did nothing to fix the problem.

Answer 1

The direct cause for the error is that for an empty list as input, the check left == right will not be true and then your code goes on to access nums[mid], which is invalid.

But taking a step back, your algorithm will not work. RC cannot help to update the indices correctly, as if you would only narrow down a list by steps of 1 (which is not what binary search does). Take for instance input [1, 1, 1, 1, 1, 1] and finding 1...

What you need is two binary searches: one that will find the start of the sublist that has the targeted value, and another that will find the end of that same sublist.

Spoiler solution:

from operator import lt, le class Solution(object): def searchRange(self, nums, target): def search(low, high, cmp): while low < high: mid = (low + high) // 2 if cmp(nums[mid], target): low = mid + 1 else: high = mid return low i = search(0, len(nums), lt) # find left-most occurrence if i == len(nums) or nums[i] != target: # not found return [-1, -1] return [i, search(0, len(nums), le) - 1] # find right-most

With bisect it becomes peanuts:

from bisect import bisect_left, bisect_right class Solution(object): def searchRange(self, nums, target): i = bisect_left(nums, target) if i == len(nums) or nums[i] != target: # not found return [-1, -1] return [i, bisect_right(nums, target) - 1]