java - 检查数组中的值是否对应于它的位置

Question

不久前我遇到了一个算法问题。

我需要查找存储在数组中的值是否在它的“位置”。一个例子会更容易理解。

让我们采用数组 A = {-10, -3, 3, 5, 7}。该算法将返回 3，因为数字 3 位于 A[2](第 3 位)。相反，如果我们采用数组 B = {5, 7, 9, 10}，算法将返回 0 或 false 或其他任何值。

数组总是排序的!

我无法找到复杂度高的解决方案。 (单独查看每个值并不好!)也许可以通过使用类似于合并排序的方法来解决该问题，方法是将其切成两半并对其进行验证？

有人可以帮我解决这个问题吗？Java 算法会是最好的，但伪代码也会对我有很大帮助!

Answer 1

这是一种算法(基于二分查找)，用于查找所有匹配索引，其最佳情况复杂度为 O(log(n))，最坏情况复杂度为 O(n):

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

2-如果值数组[m]严格小于m，你可以忽略数组的左半部分(从索引0到索引m-1)，递归地应用到右半部分。

3-如果array[m]==m，向计数器加一并递归地应用于两半

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

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