有一個有序數(shù)組arr十厢，其中不含有重復元素，請找到滿足arr[i]==i條件的最左的位置爷耀。如果所有位置上的數(shù)都不滿足條件，返回-1拍皮。
給定有序數(shù)組arr及它的大小n歹叮，請返回所求值。
測試樣例：
[-1,0,2,3],4
返回：2
思路
不含重復元素的有序數(shù)組,可以看成嚴格遞增的序列. 看到有序,自然而然想到二分查找.這里我們對題目進行一些簡化,便于理清思路.
數(shù)組的下標是嚴格增加1,可以看成一條斜率為1的直線,而數(shù)組是嚴格遞增的, 每次增長至少為1.此處為了方便大家理解,將其簡化為一條斜率>1的直線,實際上應該是折線,可能與y=x有多個交點.如下圖所示.
示意圖
如果arr[mid]<mid,交點如果存在只能在其右側,將搜索范圍變成[mid+1,hi]
同理如果arr[mid]>mid,交點如果存在只能在其左側,將搜索范圍變成[lo,mid-1]
如果arr[mid]=mid,記錄下當前位置,繼續(xù)向左尋找下一個交點.搜索范圍是[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;
}
