Python递归二分查找运行报Unhashable Type 'list'错误咨询

• 触发Unhashable Type 'list'的核心原因：list是可变不可哈希类型，不能作为字典的key使用。你没有手动写字典逻辑不代表没有字典操作，如果你给search方法添加了@lru_cache装饰器做缓存，装饰器内部会默认用字典存储入参与返回值的映射，而你递归调用时传递的切片参数是列表类型，就会触发这个报错。
• 代码本身存在多重逻辑问题：
  1. 递归调用写法错误：search是类的实例方法，递归调用时需要加self.前缀，直接调用search()会优先查找全局作用域的函数，不存在时会抛出NameError。
  2. 迭代和递归逻辑混用：递归版二分查找不需要外层的while left <= right循环，递归的终止条件本身就可以处理边界判断，二者混用会导致逻辑混乱。
  3. 索引偏移错误：你递归时传递的是切片后的新列表，返回的索引是新列表的下标，而非原输入数组的下标，就算解决了报错问题，返回的结果也不符合要求。

推荐使用左右指针传参的递归写法，不需要对数组切片，既避免了不可哈希的问题，也不会出现索引偏移错误，执行效率更高：

from typing import List

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # 内部递归函数仅传递左右边界指针
        def dfs(left: int, right: int) -> int:
            # 递归终止条件：区间无有效元素
            if left > right:
                return -1
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                return dfs(left, mid - 1)
            else:
                return dfs(mid + 1, right)
        
        return dfs(0, len(nums) - 1)

如果你坚持要使用切片传参的写法，需要做以下修改：

1. 移除search方法上的@lru_cache装饰器
2. 递归调用时添加self.前缀
3. 计算返回值时补充切片的索引偏移量
   示例代码如下：

from typing import List

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1
        mid = len(nums) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] > target:
            return self.search(nums[:mid], target)
        else:
            # 右半部分的返回结果需要加上mid+1的偏移量，才是原数组的索引
            right_res = self.search(nums[mid+1:], target)
            return right_res + mid + 1 if right_res != -1 else -1

内容的提问来源于stack exchange，提问作者STShark