题目:假设一个单调递增的数组里的每个元素都是整数并且是唯一的。请编程实现一个函数,找出数组中任意一个数值等于其下标的元素。例如,在数组 {-3, -1, 1, 3, 5} 中,数字 3 和它的下标相等。
思路 1:遍历
最直观的思路是:从左到右遍历有序数组,直到找到数字与下标相等的数字。该算法的时间复杂度是 O(n)。我们可以找到更快的算法。
思路 2:二分查找
在有序数组中查找数字,首先想到的就是二分查找。思路是:使用二分查找算法找到数字与下标相等的数字。
二分查找的过程如下:中间的数字与下标比较,如果等于下标,则是我们要找的;如果数字小于下标,说明目标数字在右半段,对右半段进行二分查找;如果数字大于下标,说明数字在左半段,对左半段进行二分查找。
该算法的时间复杂度是 $O(log\,n)$。