python递归二分查找问题中的类型错误

Question

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        
        while left <= right:
            curr_ind = (right+left)//2
            print(nums[curr_ind + 1:len(nums)])
            if nums[curr_ind] == target:
                return curr_ind
            elif nums[curr_ind] > target:
                return search(nums[left:curr_ind], target)
            elif nums[curr_ind] < target:
                return search(nums[curr_ind + 1:len(nums)], target)
            
        return -1

我在倒数第二行中收到 Unhashable Type 'list' 错误。 我认为我在这个问题中没有使用字典，但我不确定为什么它会给我这个错误。

Answer 1

我认为你错误地使用了递归，试试这个：

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        
        while left <= right:
            curr_ind = (right+left)//2
            print(nums[curr_ind + 1:len(nums)])
            if nums[curr_ind] == target:
                return curr_ind
            elif nums[curr_ind] > target:
                right = curr_ind - 1
            elif nums[curr_ind] < target:
                left = curr_ind + 1
            
        return -1

Answer 2

class Solution:
    def bs(self, current:List[int], left: int, target: int) -> int:
        if len(current) == 1:
            return left if current[0] == target else -1
        index = len(current) >> 1
        if current[index] < target:
            return self.bs(current[index:], left + index, target)
        elif current[index] > target:
            return self.bs(current[:index], left, target)
        else:
            return left + index

    def search(self, nums: List[int], target: int) -> int:
        return self.bs(nums, 0, target)