{1,22,56,53,34,51,77}这是一个数组，如何不用内部函数和遍历数组的方法判断出 53 在这个数组里。（面试问题）

[ning1022]

我想到了php中的in_array()函数。但是很明显不对。

[ning1022]

@nozama 牛，崇拜！

[luoxun]

array_flip
然后 array_key_exists
应该最快吧 ?

[Hashell]

http://3v4l.org/AdKW4

递归

[ning1022]

@luoxun 这个用了php内部函数了，我感觉会快些，因为用数字查询比较吧，但是跟in_array()相比也没啥区别！

[sandideas]

那个随机数的为什么不直接遍历前6个。。
这样也有七分之一的概率不需要遍历所有。。。

[ning1022]

@Hashell 这个方法好，我看了，可以，感觉递归有可能是正确答案，但是好像这也是一种遍历！

[luoxun]

@sandideas 如果是面试 我觉得 递归和 array_flip 都应该算是正解 起码说得过去

[Felldeadbird]

递归算遍历吗？我只想到递归了。

[ghostcat]

以前我面试也被问了这个问题……实在想不出比遍历更快的方法，然后一直不知道答案

[sandideas]

@luoxun 基本上就是递归了。。。不过这个的递归想不到什么巧妙的方法。直接简单的递归太没意思了

[sablib]

请定义 遍历 。。。
如果说 ·遍历· 是指按照索引顺序的话，那当然是可以做到不用·遍历·。。。

[procen424]

如果说遍历是指完整的访问了每一个数，那么对于某些数，只访问其中的一部分二进制位（最少为 1 个位）是不是一种符合条件的解法？
比如说，用每个数的最低位与待查找数的最低位做位与，相同的挑出来，再比较次低位，以此类推。
对于这个题来说，如果是 int32 的数组，共 224 个 bit，读取了其中的 44 个 bit 之后确认了 53 的存在，仅仅访问了 19.6% 的数据，是不是不算是严格意义上的遍历呢。
当然实际情况下你只能按字节读取，即便这样也仅访问了 35.7% 的数据而已。
然并卵，你硬说它是遍历它确实也是。。。

[Reficul]

递归是遍历的一种方法而已啊，类似遍历二叉树，可以有递归或者非递归的两种算法。这个题目用递归写本质上还是遍历了哇，并且占有内存上还比直接一个个读来的大= =

[feiyuanqiu]

我觉得出题人是想考楼主手写排序和二分的，估计是题目没写清楚...
递归也算遍历，但是没办法，这个题不用遍历做不了
写了一个递归的：

$arr = [1, 22, 56, 53, 34, 51, 77];

function _find($arr, $search, $left, $right)
{
if ($left > $right)
return false;

$pivot = rand($left, $right);
return $arr[$pivot] == $search
? true
: _find($arr, $search, $left, $pivot-1) || _find($arr, $search, $pivot+1, $right);

}

$found = _find($arr, 53, 0, count($arr)-1);

http://3v4l.org/FFFZp

[Andiry]

@procen424 思路不错，不过现在CPU cache都是64byte，你读int的一个字节等于读了整个int

[zhangsoledad]

不用遍历我也是笑了 这是数组不是hash 面试官傻逼别跟着一帮人 学过数据结构么？

[ChangxuBlack]

建议楼主了解一下布隆过滤器

[Septembers]

@ChangxuBlack
Bloom Filter的大致原理是 先 遍 历 一 次 计 算 得 到 HashSet
第二次通过索引HashSet直接命中目标元素 所以仍然无法避免 遍 历
see https://en.wikipedia.org/wiki/Bloom_filter

我前面提到的方法："构造随机数作为索引随机命中" 理论理想的情况下可以避免 遍历


@zhangsoledad PHP的array在Zend Engine的实现就是HashTable
see https://github.com/reeze/tipi/blob/master/book/chapt03/03-01-00-variables-structure.markdown#二变量的值存储

[Andiry]

@ChangxuBlack 单给你一个数组哪来的bloom filter

@Septembers 你这个跟遍历没有区别，期望值是一样的

[jesse0628]

hash table 不行？