问检查Array中的值是否与其位置相对应

EN

下面是一种算法(基于二进制搜索)，用于查找最佳情况复杂度为O(log(n))和最坏情况复杂度为O(N)的所有匹配索引：

1-检查位置m= array.length /2处的元素

2-如果arraym值严格小于m，则可以忽略数组的左侧(从索引0到索引m-1)，并递归地应用到右侧。

3-如果是arraym==m，将一个添加到计数器中，并递归地应用于两部分

4-如果是arraym>m，忘记数组的右半部分，递归地应用到左侧。

在这里，使用线程可以加快速度。我想数组中没有重复。

如果要在数组中找到位于自己位置的第一个数字，只需迭代数组：

static int find_in_place(int[] a) {
    for (int i=0; i<a.length; i++) {
        if (a[i] == i+1) {
            return a[i];
        }
    }
    return 0;
}

它的复杂度为O(n)，平均成本为n/2。

如果没有这样的元素，可以通过添加一个特殊条件来跳过迭代。

if(a[0]>1 && a[a.length-1]>a.length){
    //then don't iterate through the array and return false
    return false;
} else {
    //make a loop here
}