我在一次面试中被问到以下问题。
给定一个大小未知的输入数组，所有的1都在开头，0在结尾。在数组中从0开始的位置查找索引。假设数组中有数百万个1和0。即数组非常大。。例如数组内容1111111……1100000……0000000。后来在谷歌上搜索这个问题时，我在上找到了这个问题http://www.careercup.com/question?id=2441。
这个问题最令人困惑的是，如果我不知道数组的大小，我怎么知道*(array_name+index)是否属于数组？？即使有人找到了一个值从1变为0的索引，如何断言该索引属于数组。
我能找到的最好的答案是O(logn)解，其中保持索引加倍，直到找到0。同样，什么是特定元素属于数组的保证。
编辑：它是一个基于c的数组。限制是您没有结束elem的索引(不能使用sizeof(arr)/sizeof(arr[0]))。如果我是1024.arr[1024]==1怎么办。arr[2048]越界，因为数组长度为1029(程序员未知)。那么，在寻找解决方案时可以使用arr[2048]吗？它是越界的，它的价值可以是任何东西。所以我想知道这个问题可能有缺陷。
如果你不知道数组的长度，并且无法读取数组的末尾(因为它可能会出错或给你随机垃圾)，那么你能做的只有的的事情就是从头开始，查看每个元素，直到找到零：
int i = 0;
while (a[i] != 0) i++;
return i;
你最好希望在数组中至少有一个零。
如果可以以某种方式找出数组的长度，那么二进制搜索确实更有效。
Ps。如果它是一个char数组，那么只在上面调用strlen()会更容易，也可能更快。上面的代码与strlen()差不多，只是标准库实现可能会更好地针对您的CPU架构进行优化。
我会使用二进制搜索来找到0。
一开始你在中间，如果是1，你在右边，否则在左边。继续这样做，直到找到第一个0。
现在，问题语句说：给定一个大小未知的输入数组，所有的1在开头，0在结尾。数组在内存中的表示方式是一个接一个的元素，因此，由于您知道数组末尾有0，如果您的算法工作正常，那么*(Array_name+index)肯定属于该数组。
编辑：
对不起，我刚刚意识到，只有当你知道尺寸时，这个解决方案才有效。否则，是的，将索引加倍也是我想到的最好的算法。但是，索引仍然属于数组这一事实的证据是相同的。
因评论而编辑：
它表示在数组的末尾有0。因此，如果你做一个简单的
int i;
while(i)
if( *(array_name+i) != 1 )
return i;
它应该给你第一个索引，对吧？既然你知道这个数组看起来像1111…000000，你也知道0中至少有1个，这是第一个，肯定属于这个数组。
在您的情况下，您通过加倍索引进行搜索，然后使用index和index/2之间的二进制搜索。在这里，你不能确定index是否属于数组，但index和index/2之间的第一个0肯定属于数组(语句说至少有一个0)。
Upps。。。我刚刚意识到，如果你继续将索引加倍，然后离开数组，你会发现"垃圾值"，这意味着它们可能不是0。因此，你能做的最好的事情就是检查第一个0，而不是第一个不是0的元素。遗憾的是，可能存在值为1的垃圾值(可能性极小，但可能会发生)。如果是这种情况，您将需要使用O(n)算法。
如果您不知道数组的大小，可以从index = 1开始；在每一步中，您都要检查2 * index是否大于数组的长度——如果是或是零——现在您有了一个边界来开始二进制搜索；否则为CCD_ 6。