分析

该题用二分查找的思想进行编程和求解。

代码实现

#include <bits/stdc++.h>
using namespace std;
int search(int arr[],int low,int high){
    while(low<=high){
        int mid=(low+high)/2;
        if(arr[mid]>mid){
            high=mid-1;
        }else if(arr[mid]<mid){
            low=mid+1;
        }else{
            return 1; // 1表示有 
        }
    }
    return 0;//0表示无 
}
int main(){
    int arr[6]={0,2,5,6,8,9};
    int n=6;
    int low=0;
    int high=n-1;
    cout<<search(arr,0,n-1);
}

需要说明的：

在第6行，因为数组都是整数，且是升序的，故而当 arr[mid]>mid 时， min(arr[mid])=mid+1,min(arr[mid+1])=mid+2 依此类推，所以可以判定下标[mid,high]都不满足条件，需要舍去，故而让 high=mid-1,让程序在 low~mid-1 的范围内搜索符合条件的下标。
第8行类似。