I would like to ask why this part if j == len(nums) or nums[j] != target: return 0 can be executed when it returns -1, but not when it returns 0? And is there any other problem with the whole code block?
Here's the full code:
class Solution(object):
def search(self, nums, target):
# find the right bound
i, j = 0, len(nums) - 1
while i <= j:
m = (i + j) // 2
if nums[m] < target:
i = m + 1
elif nums[m] > target:
j = m - 1
else:
i = m + 1
right = i
if j == len(nums) or nums[j] != target:
return 0
# find the left bound
i, j = 0, len(nums) - 1
while i <= j:
m = (i + j) // 2
if nums[m] < target:
i = m + 1
elif nums[m] > target:
j = m - 1
else:
j = m - 1
left = j
if i == len(nums) or nums[i] != target:
return 0
return right - left - 1
Your code does not account for the case where the nums list is empty. In such a case, j will be -1 (len(nums)-1).
Thus, an IndexError occurs in nums[j] != target as -1 is not a valid index for an empty list.
Additionally, the condition j == len(nums) or i == len(nums) will never be true as i and j are bounded by 0 and len(nums)-1 (their initial values).
Therefore, your code should be
class Solution(object):
def search(self, nums, target):
# account for empty lists
if len(nums) == 0:
return 0
# find the right bound
i, j = 0, len(nums) - 1
while i <= j:
m = (i + j) // 2
if nums[m] < target:
i = m + 1
elif nums[m] > target:
j = m - 1
else:
i = m + 1
right = i
if nums[j] != target:
return 0
# find the left bound
i, j = 0, len(nums) - 1
while i <= j:
m = (i + j) // 2
if nums[m] < target:
i = m + 1
elif nums[m] > target:
j = m - 1
else:
j = m - 1
left = j
if nums[i] != target:
return 0
return right - left - 1