最优算法问题

Question

有一递增整数序列A1<A2<A3...<An已存入数组，返回是否存在i,使Ai=i.我写的伪代码如下：public boolean find(int[] arr){
  
  //Assume array index begin from 1.
  int k=arr.length;
  if(arr[k]<=0)  //if An<=0, positive i cannot equal all the Ai
      return false;
  for(int i=k;i>0;i--){  //check from the end to save time if there are negative integers.
     if(arr[i]==i){
       return true;
       break;
       }
     if(arr[i]<=0) break;   }
  return false;
}这个算法的worst-case时间复杂度是O(n),但是我觉得应该还有更有效的算法，但是实在想不出来。各位大哥能否指点一下，太感谢了bow:)

Answer 1

既然是整数序列，Ai+1 - Ai >= 1
 => Ai+1 - (i+1) >= Ai - i
令Bi = Ai - i ，得到B1 <=B2 <=B3... <=Bn
所以只要用二分法找Bi = 0
可以考虑用Arrays.binarySearch方法

Answer 2

看看，这样是否可以？  public boolean find(int[] arr)
    {
        if (arr == null)
        {
            return false;
        }
        
        int left = 0;
        int right = arr.length -1;
        
        while (left <= right)
        {
            int middle = (left + right) / 2;
            if (middle == arr[middle])
            {
                return true;
            }
            
            if (middle > arr[middle])
            {
                left = middle + 1;
            }
            else
            {                
                right = middle -1;               
            }
        }
        return false;

Answer 3

递归实现二分查找:
int binarySearch(int[] a, int x, int n) {
int left = 0;
int right = n - 1;
while (left <= right) {
int middle = (left + right) / 2;
if (x == a[middle])
return middle;
if (x > a[middle])
left = middle + 1;
else
right = middle - 1;
}
return -1;
}

Answer 4

这个才是递归
int binary_search(int[] r, int low, int high, int k) {
int mid = (low + high) / 2;
if (low < high) {
if (k <= r[mid])
return binary_search(r, low, mid, k);
else
return binary_search(r, mid + 1, high, k);
} else if (low == high) {
if (k == r[mid])
return low;
else
return -1;
} else {
return -1;
}
}