采访Q：给定一个大小未知的输入数组，开始时全为1，最后为0。找到从0开始的数组中的索引

Question

我在面试中被问到以下问题。

给定一个大小未知的输入数组，其中所有1都在开头，0到最后。从0开始的位置找到数组中的索引。考虑在数组中有数以百万计的1和0。数组非常大..数组内容1111111 ....... 1100000 ......... 0000000.On后来用google搜索这个问题，我发现关于http://www.careercup.com/question?id=2441的问题。

这个问题最令人费解的是如果我不知道数组的大小，我怎么知道*（array_name + index）属于数组？即使有人发现索引的值从1变为0，如何声明索引属于数组。

我可以找到的最佳答案是O（logn）解决方案，其中一个人保持倍增索引，直到找到0.再次保证特定元素属于数组。编辑： 这是一个基于c的数组。约束是你没有end elem的索引（不能使用sizeof（arr）/ sizeof（arr [0]））。如果我说1024.arr [1024] == 1会怎么样。由于数组长度为1029（程序员未知），所以arr [2048]不受约束。那么在找到解决方案时使用arr [2048]可以吗？它是无界的，它的价值可以是任何东西。所以我想知道，也许这个问题是有缺陷的。

Answer 1

如果你不知道数组的长度，并且不能读过去数组的末尾（因为它可能会出现段错误或给你随机垃圾），那么只有你可以做的事情是开始从一开始，并期待在每一个元素，直到找到一个零：

int i = 0; 
while (a[i] != 0) i++; 
return i; 

你最好希望有是阵列中至少一个零。

如果你可以以某种方式找出数组的长度，那么二分查找确实更有效。

Ps。如果这是一个char阵列，那么只需拨打strlen()就可以更快，更容易。上面的代码几乎是strlen()所做的，除了标准库实现可能会更好地针对您的CPU架构进行优化。

Answer 2

我会用二进制搜索去以便找到0

起初，你走中间，如果是1，你在右边走，否则在左侧。继续这样做，直到找到第一个为止。

现在，问题陈述是：给定一个大小未知的输入数组，其中开始时为全1，输入数组为0。数组在内存中的表现方式是1个元素，因此，因为您知道数组末尾有0，所以如果您的算法正常工作，那么*（array_name + index）肯定属于该数组。

编辑：

对不起，我只是意识到，如果你知道的大小解决方案仅适用。否则，将索引加倍是我脑海中最好的算法。但是索引仍然属于数组的事实的证明是相同的。

由于编辑评论：

它指出，在数组的结束还有0。因此，如果你做一个简单的

int i; 
while(i) 
    if(*(array_name+i) != 1) 
     return i; 

它应该给你第一个索引，对不对？ 现在既然你知道数组看起来像1111 ... 000000，你也知道0中至少有1个是第一个，肯定属于数组。

在你的情况下，你通过加倍索引然后在索引和索引/ 2之间使用二分搜索来进行搜索。在这里，你不能确定索引是否属于数组，但索引和索引/ 2之间的前0肯定属于数组（声明表示至少有一个0）。

Uppss ...我只是意识到，如果你保持倍增索引，你走出数组，你会发现“垃圾值”，这意味着他们可能不是0的。所以你可以做的最好的事情不是检查第一个0是否检查第一个非0的元素。可悲的是，可能存在值为1的垃圾值（极小的机会，但可能发生）。如果是这种情况，您将需要使用O（n）算法。

Answer 3

如果你不知道数组的大小，你可以从index = 1开始;在每一步中，您检查2 * index是否大于数组长度 - 如果是或是否为零 - 现在您有一个边界来开始二分查找;否则index = 2 * index。