blocks|key|1091878|text|您可以执行二进制搜索:搜索中间，如果值低于索引，则更低的索引将不包含相同的值。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1091879|然后搜索较高的一半，并继续搜索，直到找到元素，或达到一个元素跨度。|1091880|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|F|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|G|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|H|8|@]|9|@]|A|$]]]|E|$]]

You can perform a binary search:
search the middle, if the value is lower than the index, than no lower index will contain the same value.

Then you search the higher half, and continue till you find the element, or reach one element span.

blocks|key|1091917|text|在我看来，做二进制拆分可能会更快。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1091918|看看中值，如果它是高的，那么你需要的是什么，在下半部分重新搜索。|1091919|经过一次比较，您已经将数据集一分为二|1091920|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|H|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|I|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|J|8|@]|9|@]|A|$]]|$1|F|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|G|$]]

of the top of my head, doing binary splitting might be faster.

look at the middle value, if it is high then what you need, re-search in the lower half.

After one comparison, you have already spilt your data set in half

blocks|key|1091963|text|我认为这样会更快。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1091964|从列表的中间开始|1091965|如果Xi+>I，则转到剩余左侧的中间|1091966|如果Xi+|1091967|继续这样做，它将减少每个循环的可能元素数量的一半|1091968|
|1091969|1091970|entityMap^0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|O|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|P|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|Q|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|R|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|S|8|@]|9|@]|A|$]]|$1|J|3|K|5|6|7|T|8|@]|9|@]|A|$]]|$1|L|3|-4|5|6|7|U|8|@]|9|@]|A|$]]|$1|M|3|-4|5|6|7|V|8|@]|9|@]|A|$]]]|N|$]]

I think this would be faster.

Start in the middle of the list

If X[i] > i then go to the middle of the remaining left side

if X[i] &lt; i then go the middle of the remaining right 

Keep doing that and it will reduce the number of possible elements by half for each loop

blocks|key|877397|text|在阅读了问题之后，似乎有一个场景可以用来加快查找速度。当比较该位置与该值时，如果该值大于该位置，则该值可用作下一个要评估的位置。这将有助于更快地跳过数组。可以这样做，因为数组是排序的。我们跳过的值在概念上移到了数组中的左侧，并且位于错误的位置。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|877398|示例：|877399|int+ABC[]+=+{+-2,+-5,+4,+7,+11,+22,+55+};|code-block|syntax|javascript|877400|如果我的当前位置是2，并且它的值为4，它们就不相等，从概念上讲，值4会向左移位。我可以使用值4作为我的下一个位置，因为如果值4是错位的，那么小于4的值也是错位的。|877401|一些示例代码只是为了讨论：|877402|void+main()
{
++++int+X[]+=+{+-3,+-1,+0,+3,+5,+7};
++++int+length+=+sizeof(X)/sizeof(X[0]);

++++for+(int+i+=+0;+i+<+length;)+{
++++++++if+(X[i]+>+i+&&+X[i]+<+length)
++++++++++++i+=+X[i];+++++++++++++++++//+Jump+forward!
++++++++else+if+(X[i]+==+i)+{
++++++++++++printf("found+it+%25i",+i);
++++++++++++break;
++++++++}+else
++++++++++++%2B%2Bi;
++++}
}|877403|entityMap^0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|Q|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|R|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|S|8|@]|9|@]|A|$G|H]]|$1|I|3|J|5|6|7|T|8|@]|9|@]|A|$]]|$1|K|3|L|5|6|7|U|8|@]|9|@]|A|$]]|$1|M|3|N|5|F|7|V|8|@]|9|@]|A|$G|H]]|$1|O|3|-4|5|6|7|W|8|@]|9|@]|A|$]]]|P|$]]

After reading the question it seems like there is one scenario that can be used to speed up the lookup. When comparing the position to the value, if the value is greater then the position then the value can be used as the next position to evaluate. This will help jump through the array faster. This can be done because the array is sorted. The values that we are skipping are conceptually shifted to the left in the array and are in the wrong location.

Example:

<pre><code>int ABC[] = { -2, -5, 4, 7, 11, 22, 55 };
</code></pre>

If my current position is 2 and it has a value of 4 they are not equal and conceptually the value 4 is shifted to the left. I can use the value of 4 as my next position because if the value 4 is out of position then everything less then 4 is out of position as well. 

Some example code just for the sake of discussion:

<pre><code>void main()
{
 int X[] = { -3, -1, 0, 3, 5, 7};
 int length = sizeof(X)/sizeof(X[0]);

 for (int i = 0; i &lt; length;) {
 if (X[i] &gt; i &amp;&amp; X[i] &lt; length)
 i = X[i]; // Jump forward!
 else if (X[i] == i) {
 printf("found it %i", i);
 break;
 } else
 ++i;
 }
}
</code></pre>

blocks|key|877459|text|我想修改过的二进制搜索版本就足够了|type|unstyled|depth|inlineStyleRanges|entityRanges|data|877460|假设序列是|877461|Array+:+-1+1+4+5+6
Index+:++0+1+2+3+4

Result+:+1|code-block|syntax|javascript|877462|或|877463|Array+:+-2+0+1+2+4+6+10
Index+:++0+1+2+3+4+5+6+

Result:+4|877464|从这两个例子中我们可以看到，如果中间<中间，那么所需的结果永远不会在右边。伪代码看起来像这样|877465|mid+<-+(first+%2B+last+)/2

if+a[mid]+==+mid+then
+++++++return+mid

else+if+a[mid]+<+mid+then
++++++++recursive+call+(a,mid%2B1,last)

else+
+++++++++recursive+call+(a,first,mid-1)|877466|entityMap^0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|S|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|T|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|U|8|@]|9|@]|A|$G|H]]|$1|I|3|J|5|6|7|V|8|@]|9|@]|A|$]]|$1|K|3|L|5|F|7|W|8|@]|9|@]|A|$G|H]]|$1|M|3|N|5|6|7|X|8|@]|9|@]|A|$]]|$1|O|3|P|5|F|7|Y|8|@]|9|@]|A|$G|H]]|$1|Q|3|-4|5|6|7|Z|8|@]|9|@]|A|$]]]|R|$]]

Modified version of Binary Search would suffice I guess

Suppose the sequence is 

<pre><code>Array : -1 1 4 5 6
Index : 0 1 2 3 4

Result : 1
</code></pre>

or

<pre><code>Array : -2 0 1 2 4 6 10
Index : 0 1 2 3 4 5 6 

Result: 4
</code></pre>

From both the examples we see that the required result will never lie on the right side if mid &lt; a[mid]... pseudocode would look something like this

<pre><code>mid &lt;- (first + last )/2

if a[mid] == mid then
 return mid

else if a[mid] &lt; mid then
 recursive call (a,mid+1,last)

else 
 recursive call (a,first,mid-1)
</code></pre>

blocks|key|1092093|text|Java：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1092094|public+static+boolean+check+(int+[]+array,+int+i)
{
++++if+(i+<+0+%7C%7C+i+>=+array.length)
++++++++return+false;

++++return+(array[i]+==+i);
}|code-block|syntax|javascript|1092095|C%2B%2B：|1092096|bool+check+(int+array[],+int+array_size,+int+i)
{
++++if+(i+<+0+%7C%7C+i+>=+array_size)
++++++++return+false;

++++return+(array[i]+==+i);
}|1092097|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|M|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|N|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|O|8|@]|9|@]|A|$]]|$1|I|3|J|5|D|7|P|8|@]|9|@]|A|$E|F]]|$1|K|3|-4|5|6|7|Q|8|@]|9|@]|A|$]]]|L|$]]

Java:

<pre><code>public static boolean check (int [] array, int i)
{
 if (i &lt; 0 || i &gt;= array.length)
 return false;

 return (array[i] == i);
}
</code></pre>

C++:

<pre><code>bool check (int array[], int array_size, int i)
{
 if (i &lt; 0 || i &gt;= array_size)
 return false;

 return (array[i] == i);
}
</code></pre>

blocks|key|1092169|text|它不需要像@codaddict在answer中建议的那样考虑任何数组Y。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1092170|使用二进制搜索并检查给定数组的中间元素，如果它低于它的索引，那么我们不需要检查任何较低的索引，因为该数组是排序的，所以如果我们向左移动，减去m个索引和(至少)m值，所有后续元素也将太小。例如，如果是arr[5]+=+4，则是arr[4]+<=+(4+-+1)和arr[3]+<=+(4+-+2)，依此类推。如果中间元素大于其索引，则可以应用类似逻辑。|1092171|下面是简单的Java实现：|1092172|int+function(int[]+arr)+{
++++++++int+low+=+0;
++++++++int+high+=+arr.length+-+1;

++++++++while(low+<=+high)+{
++++++++++++int+mid+=+high+-+(high+-+low)+/+2;

++++++++++++if(arr[mid]+==+mid)+{
+++++++++++++++++return+mid;
++++++++++++}+else+if(arr[mid]+<+mid)+{
+++++++++++++++++low+=+mid+%2B+1;
++++++++++++}+else+{
+++++++++++++++++high+=+mid+-+1;
++++++++++++}
++++++++}

++++++++return+-1;+//+There+is+no+such+index
}|code-block|syntax|javascript|1092173|请注意，只有当所有元素都是不同的时，上述解决方案才有效。|1092174|entityMap|0|LINK|mutability|MUTABLE|url|https://stackoverflow.com/a/4172612/301444^0|Y|1|G|6|0|0|2R|A|34|H|3M|H|0|6|4|0|0|0^^$0|@$1|2|3|4|5|6|7|Y|8|@$9|Z|A|10|B|C]]|D|@$9|11|A|12|1|13]]|E|$]]|$1|F|3|G|5|6|7|14|8|@$9|15|A|16|B|C]|$9|17|A|18|B|C]|$9|19|A|1A|B|C]]|D|@]|E|$]]|$1|H|3|I|5|6|7|1B|8|@$9|1C|A|1D|B|C]]|D|@]|E|$]]|$1|J|3|K|5|L|7|1E|8|@]|D|@]|E|$M|N]]|$1|O|3|P|5|6|7|1F|8|@]|D|@]|E|$]]|$1|Q|3|-4|5|6|7|1G|8|@]|D|@]|E|$]]]|R|$S|$5|T|U|V|E|$W|X]]]]

Its not require to think in terms of any array <code>Y</code> as suggested in <a href="https://stackoverflow.com/a/4172612/301444">answer</a> by @codaddict.

Use binary search and check the middle element of given array, if it is lower than its index, than we do not need to check for any lower index because the array is
sorted and so if we move to the left, subtracting m indexes and (at least) m value, all subsequent elements will also be too small. E.g. if <code>arr[5] = 4</code> then <code>arr[4] &lt;= (4 - 1)</code> and <code>arr[3] &lt;= (4 - 2)</code> and so on. Similar logic can be apply if middle element is greater than its index.

Here is simple <code>Java</code> implementation:

<pre><code>int function(int[] arr) {
 int low = 0;
 int high = arr.length - 1;

 while(low &lt;= high) {
 int mid = high - (high - low) / 2;

 if(arr[mid] == mid) {
 return mid;
 } else if(arr[mid] &lt; mid) {
 low = mid + 1;
 } else {
 high = mid - 1;
 }
 }

 return -1; // There is no such index
}
</code></pre>

Note that the above solution would work only if all elements are distinct.

blocks|key|877605|text|这是我想出来的一个解决方案，如果有重复的话它就会起作用(我错误地忽略了没有重复的警告)。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|877606|//invariant:+startIndex+<=+i+<=+endIndex

int+modifiedBsearch(int+startIndex,+int+endIndex)
{
+++int+sameValueIndex+=+-1;
+++int+middleIndex+=+(startIndex+%2B+endIndex)+/2;
+++int+middleValue+=+array[middleIndex];
+++int+endValue+=+array[endIndex];
+++int+startValue+=+array[startIndex];

+++if(middleIndex+==+middleValue)
++++++return+middleValue;
+++else+{
++++++if(middleValue+<=+endIndex)
+++++++++sameValueIndex+=+modifiedBsearch(middleIndex+%2B+1,+endIndex)

++++++if(sameValueIndex+==+-1+&&+startValue+<=+middleIndex)
+++++++++sameValueIndex+=+modifiedBsearch(startIndex,+middleIndex+-1);
+++}

+++return+sameValueIndex;

}|code-block|syntax|javascript|877607|我猜这需要O(log+)时间，但第一眼看起来并不清楚？|877608|如果你不走运，它将花费O(n+log+n)时间(堆栈树的高度将是log+n，它将是一棵完整的树，n个节点在最后一层，n/2在倒数第二层，依此类推)。|877609|因此，平均而言，它将介于O(log+)和O(+n+)之间。|877610|entityMap^0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|O|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|P|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|Q|8|@]|9|@]|A|$]]|$1|I|3|J|5|6|7|R|8|@]|9|@]|A|$]]|$1|K|3|L|5|6|7|S|8|@]|9|@]|A|$]]|$1|M|3|-4|5|6|7|T|8|@]|9|@]|A|$]]]|N|$]]

This is a solution I came up with, and it works if there are duplicates (I mistakenly overlooked that caveat of there being no duplicates).

<pre><code>//invariant: startIndex &lt;= i &lt;= endIndex

int modifiedBsearch(int startIndex, int endIndex)
{
 int sameValueIndex = -1;
 int middleIndex = (startIndex + endIndex) /2;
 int middleValue = array[middleIndex];
 int endValue = array[endIndex];
 int startValue = array[startIndex];

 if(middleIndex == middleValue)
 return middleValue;
 else {
 if(middleValue &lt;= endIndex)
 sameValueIndex = modifiedBsearch(middleIndex + 1, endIndex)

 if(sameValueIndex == -1 &amp;&amp; startValue &lt;= middleIndex)
 sameValueIndex = modifiedBsearch(startIndex, middleIndex -1);
 }

 return sameValueIndex;

}
</code></pre>

I would guess this takes O(log n) time, but this isn't clear in first glance???

If you're unlucky, it'll take O(n log n) time (the height of the stack tree will be log n, and it will be a full tree, with n nodes in the last level, n/2 in next to last, etc.). 

So, on average it will be between O(log n) and O(n log n).

I was asked the following question in my interview yesterday:

Consider a Java or C++ array say <code>X</code> which is sorted and no two elements in it are same. How best can you find an index say <code>i</code> such that element at that index is also <code>i</code>. That is <code>X[i] = i</code>.

As clarification she also gave me an example:

<pre><code>Array X : -3 -1 0 3 5 7
index : 0 1 2 3 4 5

Answer is 3 as X[3] = 3.
</code></pre>

The best I could think was a linear search. After the interview I though a lot on this problem but could not find any better solution. My argument is: the element with the required property can be anywhere in the array. So it could also be at the very end of the array so we need to check every element.

I just wanted to confirm from the community here that I'm right. Please tell me I'm right :)

Interview question - Search in sorted array X for index i such that X[i] = i

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

在昨天的面试中，我被问到了以下问题：考虑一个Java或C++数组，比方说X，它是经过排序的，其中没有两个元素是相同的。怎样才能找到一个索引，比如i，这样位于该索引处元素也是i。这就是X[i] = i。作为澄清，她还给了我一个例子：Array X : -3 -1 0 3 5 7index   :  0  1 2 3 4 ...

问面试问题-在排序数组X中搜索索引i，使X[i] =i
EN

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问面试问题-在排序数组X中搜索索引i，使X[i] =iEN

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问面试问题-在排序数组X中搜索索引i，使X[i] =i
EN