最左原位

有一个有序数组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;
    }