有一个有序数组arr，其中不含有重复元素，请找到满足arr[i]==i条件的最左的位置。如果所有位置上的数都不满足条件，返回-1。
给定有序数组arr及它的大小n，请返回所求值。
测试样例：
[-1,0,2,3],4
返回：2
思路
不含重复元素的有序数组,可以看成严格递增的序列. 看到有序,自然而然想到二分查找.这里我们对题目进行一些简化,便于理清思路.
数组的下标是严格增加1,可以看成一条斜率为1的直线,而数组是严格递增的, 每次增长至少为1.此处为了方便大家理解,将其简化为一条斜率>1的直线,实际上应该是折线,可能与y=x有多个交点.如下图所示.
示意图
如果arr[mid]<mid,交点如果存在只能在其右侧,将搜索范围变成[mid+1,hi]
同理如果arr[mid]>mid,交点如果存在只能在其左侧,将搜索范围变成[lo,mid-1]
如果arr[mid]=mid,记录下当前位置,继续向左寻找下一个交点.搜索范围是[lo,mid-1].
完整代码如下:
public int findPos(int[] arr, int n) {
int lo=0,hi=n-1;;
int pos=-1;
int mid=0;
if(arr[0]>=n||arr[n-1]<0)return pos;
while(lo<=hi){
mid=lo+(hi-lo)/2;
if(arr[mid]>mid)hi=mid-1;
else if(arr[mid]<mid) lo=mid+1;
else{
pos=mid;
hi=mid-1;
}
}
return pos;
}
