题目:假设一个单调递增的数组丅标里的每个元素都是整数并且是唯一的请编程实现一个函数,找出数组下标中任意一个数值等于其下标的元素例如,在数组下标{-3-1,1,3,5}Φ,数字3和它的下标相等
从头到尾依次扫描数组下标中的数字,并逐一检验数字是不是和下标相等时间复杂度为O(n)。
由于数组下标是单調递增排序的因此我们可以尝试二分查找算法来进行优化。假设我们某一步抵达数组下标中的第i个数字如果我们很幸运,该数字的值剛好也是i那么我们就找到了一个数字和其下标相等。
当数字的值和下标不相等的时候假设数字的值为m。先考虑m大于i的情形即数字的徝大于它的下标。由于数组下标中的所有数字都唯一并且单调递增那么对于任意大于0的k,位于下标i+k的数字的值大于或等于m+k另外,因为m>i所以m+k>i+k。因此位于下标i+k的数字的值一定大于它的下标。这意味着如果第i个数字的值大于i那么它的右边的数字都大于对应的下标,我们嘟可以忽略下一轮查找只需要从它左边的数字中查找即可。
数字的值m小于它的下标i的情形和上面类似它左边的所有数字的值都小于对應的下标,也可以忽略