和剑指offer 面试题53 - I. 在排序数组中查找数字 I（易）一起，构成了二分查找替代遍历思路，将时间复杂度优化至 \(O(logn)\) 的经典题目。

Question

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

示例 1:

输入: [0,1,3]
输出: 2

示例 2:

输入: [0,1,2,3,4,5,6,7,9]
输出: 8

限制：1 <= 数组长度 <= 10000

测试用例

功能测试（缺失的数字位于数组的开始、中间或者末尾）。 边界值测试（数组中只有一个数字0；或者不存在缺失。） 特殊输入测试（表示数组的指针为 nullptr指针）。

Intuition

• 如果中间元素的值和下标相等，那么下一轮查找只需要查找右半边；
• 如果中间元素的值和下标不相等，并且它前面一个元素和它的下标相等，这意味着这个中间的数字正好是第一个值和下标不相等的元素，它的下标就是在数组中不存在的数字；
• 如果中间元素的值和下标不相等，并且它前面一个元素和它的下标不相等，这意味着下一轮查找我们只需要在左半边查找即可。

Code

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        left = 0
        right = len(nums) - 1
        while left < right:
            middle = left + (right - left) // 2
            if nums[middle] == middle:  # 如果中间元素的值和下标相等，那么下一轮查找只需要查找右半边；
                left = middle + 1
            elif middle-1 >= 0 and nums[middle-1] == middle-1:  # 它前面一个元素和它的下标相等，这意味着这个中间的数字正好是第一个值和下标不相等的元素。
                return middle
            else:  # 它前面一个元素和它的下标不相等，这意味着下一轮查找我们只需要在左半边查找即可。
                right = middle
        # 很重要的判断，说明没找到不在该数组中的数字，就输出n。
        if left == len(nums) - 1 and nums[-1] == left:
            return len(nums)
        # 说明找到了不在该数组总的数字，输出left。
        else:
            return left


class TestSolution(unittest.TestCase):

    def setUp(self):
        self.test_class = Solution()

    def test_solution(self):
        # 功能测试
        inputs = [
            [0,2,3],  # 输出 1
            [0,1,2,3,4,5,6,7,9],  # 输出 8
            [0,1,3],  # 输出 2
        ]
        # 边界值的测试
        # inputs += []
        # 特殊样例
        inputs += [
            [0,1],  # 输出 2 如果没有missing，就输出n。
            [0,1,2],  # 输出 3  如果没有missing，就输出n。
            [0],  # 输出 1
            [1],  # 输出 0 missing位置在0
            [0,1,3],  # 输出 2 missing位置在最后

        ]
        # 输出的答案
        answers = [1, 8, 2, 2, 3, 1, 0, 2]
        res = []
        for i in range(len(inputs)):
            res.append(self.test_class.missingNumber(inputs[i]))
        self.assertEqual(res, answers)
 
    def tearDown(self):
        del self.test_class

if __name__ == "__main__":
    unittest.main()

Extension

Question

剑指offer 面试题53 - III. 数组中数值和下标相等的元素

假设一个单调递增的数组里的每个元素都是整数并且是唯一的。请编程实现一个函数，找出数组中任意一个数值等于其下标的元素。例如，在数组{-3，-1，1，3，5}中，数字3和它的下标相等。

测试用例

功能测试（数组中包含或者不包含数值和下标相等的元素）。 边界值测试（数组中只有一个数字；数值和下标相等的元素位于数组的开头或者结尾）。 特殊输入测试（表示数组的指针为 nullptr 指针）。

本题考点

考查应聘者的知识迁移能力。我们都知道，二分查找算法可以用来在排序数组中查找一个数字。应聘者如果能够运用知识迁移能力，把问题转换成用二分查找算法在排序数组中查找某些特定的数字，那么这些问题也就解决了一大半。 考查应聘者对二分查找算法的理解程度。这道题实际上是二分查找算法的加强版。只有对二分查找算法有着深刻的理解，应聘者才有可能解决这个问题。

Intuition

• 假设我们某一步抵达数组中的第 \(i\) 个数字。如果我们很幸运，该数字的值刚好也是 \(i\)，那么我们就找到了一个数字和其下标相等。
• 那么当数字的值和下标不相等时，假设数字的值为 \(m\)。我们先考虑 \(m\) 大于 \(i\) 的情形，即数字的值大于它的下标。由于数组中的所有数字都唯一并且单调递增，这意味着如果第i个数字的值 \(m\) 大于 \(i\)，那么它右边的数字都大于对应的下标，我们都可以忽略。下一轮查找我们只需要从它左边的数字中查找即可。
• 数字的值 \(m\) 小于它的下标 \(i\) 的情形和上面类似。它左边的所有数字的值都小于对应的下标，我们也可以忽略。下一轮查找我们只需要从它右边的数字中查找即可。

Code

class Solution:
    def correctNumber(self, nums: List[int]) -> int:
        left = 0
        right = len(nums) - 1
        while left < right:
            middle = left + (right - left) // 2
            if nums[middle] == middle: # 找到了一个数字和其下标相等的数字了
                return middle
            elif nums[middle] > middle:  # 数字的值大于它的下标。由于数组中的所有数字都唯一并且单调递增，这意味它右边的数字都大于对应的下标，我们都可以忽略。下一轮查找我们只需要从它左边的数字中查找即可。
                right = middle
            else:  # 数字的值小于它的下标。它左边的所有数字的值都小于对应的下标，我们也可以忽略。下一轮查找我们只需要从它右边的数字中查找即可。
                left = middle + 1
        return -1  # 没找到就返回-1