在一个长度为n的递增数组中,数组中元素范围是0 ~ n-1,如何在这个递增连续数组中查找缺失的数字?
分析下:
1. 排序数组中的搜索算法,首先想到的就是二分法查找
2....丢失的数字之前的左子数组:nums[m] = m, 需要找到第一个nums[m] > m的数组索引值即可....r = m-1;
这里多解释下,即使m-1这个位置是相同的, 也会被后续的左指针r=m+1的情况下处理掉,此处不好理解,需多多体会....在处理边界值的时候,在(i == r)的时候,还多需要多遍历一次,向右移动左指针一次.
4. 这时,左指针值便是最后想要的值.
所以我们的遍历条件为(l的结果值....综上,对于有序数组的查找,一般都会使用二分法查找.在查找数据的时候,注意左右边界指针的移动.以及遍历标记(l<=j)即可.