algorithm - interview Q :Given an input array of size unknown with all 1's in the beginning and 0' s in the end. 查找数组中从0开始的索引

Question

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

给定一个大小未知的输入数组，开头全为 1，结尾全为 0。从 0 开始查找数组中的索引。考虑数组中有数百万个 1 和 0。即数组非常大......例如数组内容 1111111......1100000......0000000.在后来谷歌搜索问题时，我发现关于 http://www.careercup.com/question?id=2441 的问题.

这道题最令人费解的是，如果我不知道一个数组的大小，我怎么知道*(array_name + index)是否属于这个数组？？即使有人找到一个值从 1 变为 0 的索引，如何断言该索引属于数组。

我能找到的最佳答案是 O(logn) 解决方案，其中一个人将索引加倍直到找到 0。同样，特定元素属于数组的保证是什么。

编辑: 这是一个基于 c 的数组。约束是你没有结束元素的索引(不能使用 sizeof(arr)/sizeof(arr[0]))。如果我说 1024.arr[1024]==1 怎么办。 arr[2048] 超出范围，因为数组长度为 1029(程序员未知)。那么在寻找解决方案时使用 arr[2048] 可以吗？它超出了范围，它的值可以是任何东西。所以我想知道这个问题可能有缺陷。

Answer 1

如果您不知道数组的长度，并且无法读取数组的末尾(因为它可能会出现段错误或给您随机垃圾)，那么唯一您可以做的是从头开始查看每个元素，直到找到零:

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

你最好希望数组中至少有一个零。

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

附言。如果它是一个 char 数组，那么只对其调用 strlen() 会更容易也可能更快。上面的代码几乎是 strlen() 所做的，除了标准库实现可能针对您的 CPU 架构进行了更好的优化。