在一个包含 N 个元素的已排序数组中查找一个目标值。但这个数组有点特殊,它不是一个普通的数组,而是一个“逻辑上的”数组。这个逻辑数组是由一个嵌套函数生成的。函数接收一个索引 `i`,返回该索引在逻辑数组中的值。函数是这样定义的:
``` getValue(i): if i < 0 or i >= N: return ERROR_VALUE 或者抛出异常 if i == 0: return arr[0] arr 是一个基础的、实际存在的、长度为 N 的已排序数组 else: 这里是关键:值是前一个值的某个计算结果,并且这个计算过程中可能还会再次调用 getValue return some_complex_calculation(getValue(i1)) ```
说到做过最气的题,那绝对是那道关于“无限套娃的二分查找题”。说实话,这道题本身可能并不算特别难,但是它对我造成的心理阴影和气愤程度,绝对是指数级增长的。事情是这样的,当时我在准备一个技术面试,其中有一轮是算法题。面试官给我出了一道题,大概是这样的:题目描述:在一个包含 N 个元素的已排序数组中查找一.............