面试问题 – 在sorting数组X中search索引i，使得X = i
昨天我在采访中被问及以下问题：
考虑一个Java或C ++数组，说X是sorting的，它里面没有两个元素是相同的。 如何能find一个最好的指数说， i这样的指数的元素也是i 。 那就是X[i] = i 。
作为澄清，她也给了我一个例子：
Array X : -3 -1 0 3 5 7 index : 0 1 2 3 4 5 Answer is 3 as X[3] = 3.
我能想到的最好的是线性search。 面试后，我虽然很多这个问题，但找不到更好的解决scheme。 我的观点是：具有所需属性的元素可以在数组中的任何位置。 所以它也可能在数组的最后，所以我们需要检查每个元素。
我只想在这里向社区确认我是对的。 请告诉我我是对的:)
谢谢
这可以在O(logN)时间和O(1)空间中通过稍微修改的二进制search来完成 。
考虑一个新的数组Y ，使得Y[i] = X[i] - i
Array X : -3 -1 0 3 5 7 index : 0 1 2 3 4 5 Array Y : -3 -2 -2 0 1 2
由于X中的元素数量递增 ，因此新数组Y的元素将以非递减顺序排列。 所以Y的二进制search 0会给出答案。
但创buildY将需要O(N)空间和O(N)时间。 因此，而不是创build新的数组，只需修改二进制search，使得对Y[i]的引用被replace为X[i] - i 。
algorithm：
function (array X) low = 0 high = (num of elements in X) - 1 while(low <= high) mid = (low + high) / 2 // change X[mid] to X[mid] - mid if(X[mid] - mid == 0) return mid // change here too else if(X[mid] - mid < 0) low = mid + 1; else high = mid - 1; end while return -1 // no such index exists...return an invalid index. end function
Java实现
C ++实现
有一些更快的解决scheme，平均O（log n）或在某些情况下O（log log n）而不是O（n）。 有一个谷歌的“二进制search”和“插值search” ，你可能会find非常好的解释。
如果数组是未sorting的，那么是的，该元素是在任何地方，你不能得到O（n）下，但是sorting后的数组不是这种情况。
–
根据要求对插值search进行一些说明：
虽然二进制search只关注比较两个元素的“大/小”，但是插值search也尝试使用数值 。 重点是：你有一个从0到20000的sorting值范围。你看300 – 二进制search将开始在范围的一半，在10000.插值search猜测300可能会更接近0所以它会先检查元素6000，而不是10000.然后再次 – 如果它太高，recursion到较低的子范围，并且它太低 – recursion到上部子范围。
对于具有+ – 均匀分布值的大arrays，插值search应该比二分search快得多 – 对其进行编码并亲自查看。 此外，如果首先使用一个内插search步骤，然后是一个二分search步骤，则此function效果最佳。
请注意，这是人类在字典中查找某些内容时直观的事情。
我想这会更快。
从列表中间开始
如果X [i]>我然后去到剩下的左边的中间
如果X [我]然后去剩下的权利的中间
继续这样做，每个循环都会减less一半可能的元素
它不需要根据@codaddict 回答中提出的任何数组Y来思考。
使用二进制search，并检查给定数组的中间元素，如果它低于其索引，比我们不需要检查任何较低的索引，因为数组sorting，所以如果我们移动到左边，减去m个索引和（至less）m值，所有后续元素也将太小。 例如，如果arr[5] = 4则arr[4] <= (4 - 1) arr[3] <= (4 - 2) arr[4] <= (4 - 1)和arr[3] <= (4 - 2)等等。 如果中间元素大于其索引，则可以应用类似的逻辑。
这里是简单的Java实现：
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 + 1; } else { high = mid - 1; } } return -1; // There is no such index }
请注意，上述解决scheme将工作，只有当所有元素是不同的。
您可以执行二分search：search中间，如果该值低于索引，则比较低的索引将包含相同的值。
然后你search更高的一半，并继续，直到你find元素，或达到一个元素跨度。
你的线性search想法看起来是正确的，是的。 我个人不能想到另一种方法来find价值，除非你按照你想要的价值总是在第一个元素中sorting。
编辑：好吧，我错了。 道歉！
这是我提出的一个解决scheme，如果有重复的话（我错误地忽略了没有重复的警告），它是有效的。
//invariant: startIndex <= i <= 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 <= endIndex) sameValueIndex = modifiedBsearch(middleIndex + 1, endIndex) if(sameValueIndex == -1 && startValue <= middleIndex) sameValueIndex = modifiedBsearch(startIndex, middleIndex -1); } return sameValueIndex; }
我猜这需要O（log n）的时间，但这并不清楚第一眼看到？
如果你运气不好，它会花费O（n log n）时间（堆栈树的高度是log n，它将是一棵完整树，最后一级有n个节点，下一个是n / 2最后等）。
所以平均来说，它将在O（log n）和O（n log n）之间。
是的，我相信你是对的。 没有任何对数search是可能的，因为我们没有办法来破坏我们的数据。 我们需要查看数组中的所有索引。
@Kos，我不明白如何sorting数组会有什么区别？
我的头顶，做二进制分裂可能会更快。
看中间的价值，如果是高的，那么你需要在下半部分重新search。
经过一次比较，你已经把你的数据泄露了一半
看完这个问题后，似乎有一种情况可以用来加速查找。 当比较位置和数值时，如果数值大于那个位置，则数值可以被用作下一个评估位置。 这将有助于更快地跳转arrays。 这可以做，因为数组sorting。 我们正在跳过的值在概念上被移到数组的左边，并且位于错误的位置。
例：
int ABC[] = { -2, -5, 4, 7, 11, 22, 55 };
如果我现在的位置是2并且它的值是4，那么它们在概念上是不相等的，值4被移到左边。 我可以使用4的值作为我的下一个位置，因为如果数值4不在位，那么小于4的所有数据都不在位。
一些示例代码只是为了讨论：
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 %i", i); break; } else ++i; } }
二进制search的修改版本就足够了，我猜
假设序列是
Array : -1 1 4 5 6 Index : 0 1 2 3 4 Result : 1
要么
Array : -2 0 1 2 4 6 10 Index : 0 1 2 3 4 5 6 Result: 4
从这两个例子我们看到，如果mid <a [mid] …伪代码看起来像这样，所需的结果将永远不会在右侧
mid <- (first + last )/2 if a[mid] == mid then return mid else if a[mid] < mid then recursive call (a,mid+1,last) else recursive call (a,first,mid-1)
Java的：
public static boolean check (int [] array, int i) { if (i < 0 || i >= array.length) return false; return (array[i] == i); }
C ++：
bool check (int array[], int array_size, int i) { if (i < 0 || i >= array_size) return false; return (array[i] == i); }
