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

[ning1022]

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

[adspe]

用查找算法？

[qiayue]

用 implode 合并成逗号分隔的字符串，然后判断字符串？
任何 php 内部函数都不能用吗还是说仅仅不能用同功能的函数？

[simman]

public static function inArray($item, $array) {
$flipArray = array_flip($array);
return isset($flipArray[$item]);
}

这个？？？

[xlmo]

不用内部函数？那貌似只能一个一个去if($arr[0] == 53) 了。。

[whahuzhihao]

array_flip也是内部函数啊

[iyaozhen]

应该就是考查找算法吧。

[dallaslu]

针对这个数组进行任何处理，都有可能进行遍历的吧！

如果不需要遍历，不如生成一个 0 到数组长度 -1 随机数，来随机读取数组内元素，每次保证不重复读取相同位置上就行了。这样有七分之一的概率不需要遍历数组。

[br00k]

不遍历怎么知道？？感觉这种问题怎么有点弱智啊。。。

[est]

赌10元钱任何实现都用到了某种程度上的遍历。

[choury]

不管用什么方法到最后都是要遍历的，至少得知道里面有那些元素吧
除非能找到一个公式可以生成这个序列，不然不可能的

[lincanbin]

不让遍历的意思就是不让你逐个看这里面的东西吧。
PHP内部函数1500个都不让用，又不让看。
这是什么鬼？

[mouhong]

@dallaslu 随机数生成，重复读取判断，这貌似增加复杂度了吧。数组本身无序，已经存在不需要遍历的可能性了吧。要是可接受近似解，貌似有个什么亚线性算法可以用，具体不知了

[loveuqian]

@xlmo 那也是遍历啊

[mouhong]

@mouhong 不过这种题感觉就是考个遍历，传说中的 FuzzBuzz 测试

[solupro]

我们可以用in呀
http://nikic.github.io/2012/07/27/How-to-add-new-syntactic-features-to-PHP.html

---
好吧，上面开玩笑的，也是遍历，求正确姿势

[hobbyliu]

@dallaslu 此方法，不错，忘记叫什么算法了，概率性很大。

[r00tt]

@hobbyliu 是蒙特卡洛么，有点这个的感觉

[hobbyliu]

@leepood 不是，我记得当初的一个场景时，一个猴子为了排序3个大小不同的干果，不断的往天上抛，直到，排序正确位置，适用于少量元素排序，概率性很大。

[sumhat]

$array = {1,22,56,53,34,51,77};

if (TRUE || array) {
echo '我灵光一闪，断定 53 必然在这个数组里。';
}

[101]

查找算法也是要遍历的呀

[Septembers]

@est 构造随机数作为索引随机命中 如果匹配就。。。。。？

[ning1022]

@adspe 感觉考察的是算法。但是我不也不会！

[ning1022]

@qiayue 应该是同功能的函数，比如in_array()

[est]

@Septembers 文字上可以不叫遍历，本质上不也是挨着挨着一个一个问么。

[ning1022]

@simman 我感觉这个不是正确答案！

[ning1022]

@est 我要是面试成功的话，我一定问问他这个答案，我很无语，查了很多资料，感觉是算法。

[ning1022]

@mouhong 大数据算法？感觉有点抽象！

[ning1022]

@Septembers 这个是个好思路，哈哈！

[dingyaguang117]

可以反证 必须要遍历的

[Septembers]

@ningyuqiao456 @mouhong 说的是模糊测试
see https://zh.wikipedia.org/wiki/模糊测试

[hackpro]

@dallaslu 正解 某年acm切的題
如果特別考察你算法的話 翻翻拓撲的東西 以前數學課上過 現在記不清了

[nozama]

bool find1(int num, int index, int* arr)
{
return num == arr[index];
}
bool find3(int num, int base_index, int* arr)
{
return find1(num, base_index, arr) || find1(num, base_index + 1, arr) || find1(num, base_index + 2);
}

bool find6(int num, int base_index, int* arr)
{
return find3(num, base_index, arr) || find3(base_index + 4);
}

int main()
{
int arr[] = {1,22,56,53,34,51,77};
auto found = find1(53, arr) || find6(53, 1, arr);
}

[nozama]

随手写的， 有些typo

[ning1022]

@Septembers 我感觉他考的是效率或者算法。当时我还想到了二叉树，从中间分，log2N。（以前考计算机二级的时候学的，现在都忘了，不知道对不对，呵呵）

[zhaiduo]

78

[imyip]

二分法？

[ning1022]

@nozama 你这好像没有遍历也没有内部函数，牛呀，但是我得抽空测试下，这个好像是C写的。

[dallaslu]

@ningyuqiao456 如果数组有序，二分还可以

[nozama]

@ningyuqiao456 我测试过了， 应该没错。
//====================
bool find1(int num, int index, int* arr){ return num == arr[index]; }

bool find3(int num, int base_index, int* arr){ return find1(num, base_index, arr) || find1(num, base_index + 1, arr) || find1(num, base_index + 2, arr); }

bool find6(int num, int base_index, int* arr){ return find3(num, base_index, arr) || find3(num, base_index + 4, arr); }

bool find7(int num, int* arr, size_t size){ return find1(num, 0, arr) || find6(num, 1, arr); }

int main()
{
int arr[] = {1,22,56,53,34,51,77};

auto found = find7(53, arr, sizeof(arr));

assert(found);
}

[mulog]

我觉得需要定义一下遍历。。。

[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 不行？

[proudzhu]

53 不就在这个数组里吗，一眼就能看出来，实在要写就来个 return array[3] == 53

[yuankui]

需求不明,你可以反问面试官几句
一帮助您正确理解题意

[kn007]

不可能没有遍历。。。看到有人说递归。。。递归不也是遍历。。。$i++。。

[ant_sz]

我觉得蒙特卡洛算法正解。

虽然这个算法的期望时间复杂度很高，但是来保证一定可以判断某个数字是否在array里。比如说我们把每次随机生成的下标保存在HashSet里，如果某次随机生成的下标已经在集合里我们就抛弃他。这样经过足够长的时间我们总能100%的确定53是不是在array里。（当集合size和array 的 size 相同的时候结束算法）。

[ant106]

搞不懂什么目的？

var a = [1, 2, 3, 4, 5, 6, 7];
console.log((',' + a.toString() + ',').indexOf(',3,') > 0);

转成字符串 用indexOf 算内部函数？

[WispZhan]

要求不遍历，就是二分查找了。二分查找 只有最差的情况才是遍历
排序 已经 遍历了。不遍历根本不能那个排序

[best1a]

@ant_sz +1 上面说的递归和字符串啥的，其实都算遍历的一种了

[weyou]

不让遍历无解， 那是魔术师干的事情。

[weyou]

就算是人工一眼看出53在里面， 也包含了目光的遍历。

[tushiner]

@proudzhu 大亮！

[killerv]

感觉这个比较问题扯啊，明明是个简单的问题非要复杂化。

[sirgod]

注意到53是素数所以全部乘起来再模53看是否等于0就好了

[myywin]

排序，二分？

[laoyuan]

@sirgod 终于出现正确答案了。

[013231]

@sirgod
@laoyuan
你们打算怎样把数组全部乘起来?

[VicYu]

53素数，全乘，摸53，判断是否为0

[jimiton]

@sirgod
全部乘起来，不是得遍历一遍，取出数字相乘么？
相比较遍历一遍，取数比较，有什么优势

[znoodl]

@sirgod
@laoyuan
本来遍历到一半就能确认的问题，非要遍历一遍算积再除

[sketch33]

笑死人了，还tm正确答案，真不知道是不是高级黑……

[sketch33]

这个肯定要遍历的啊，就算完全不懂编程好了，假设里面100个元素，使用某种手段访问了其中99个，发现没找到这个数字，那么剩下那个数字你是访问呢还是不访问呢

[Clarencep]

遇到这种公司，直接拜拜是最好的选择；要是进去了，还不知道会遇到什么213的产品经理呢，到那时就欲哭无泪了。

[kurtis]

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

答：function checkIf53Exist() { return true;}

！！！！！！！！！ 重要 ！！！！！！！！！！！

已知条件里已经包含53了，又没有问你任意数组，你们还争论遍历和查找个毛啊，典型的审题不清。
都是程序猿思维，我要是考官，给我说算法的人，统统OUT。

[laoyuan]

@013231 @znoodl @sketch33
怎么乘？当然是用计算器了，难不成口算？？！

function check_in_array($prime, $product) {return !($product % $prime);}
var_dump(check_in_array(53, 8718191328));

完美解决！

[laoyuan]

看那乘积，果然是大数据！

[hooluupog]

一般面试考这类东西都是考算法的。
所以这个题十有八九是让你给出一个时间复杂度小于O(n)的算法来找出某个元素。
有序数组，直接2分查找；
部分有序或者是循环有序数组，也是采用划分的思想，不过需要确定单调区间来决定每次查找的区间。
楼主给的这个数组感觉有问题啊。

[justahappy]

@laoyuan 毕竟低学历，只是个自由职业者，真不知道哪来的自信。。。。。

[laoyuan]

@justahappy 毕竟写了8年PHP，这点自信还是有的哇哈哈哈

[JackWindows]

好无聊啊，大家都在说生成随机数然后判重
正确姿势难道不是生成一个len(array)的排列，然后按这个序号去访问么？生成排列有线程算法吧

[sketch33]

@laoyuan 为了避免程序遍历整个数组，改为人工遍历整个数组。我怎么就没想到这么好的方法呢？

[ChangxuBlack]

@Septembers 好吧，我以为可以先对数组做预处理呢

[l12ab]

数组转json，然后strpos

[laoyuan]

@sketch33 对，人工遍历可以提高系统鲁棒性，比如停电什么的就不怕了

[jimiton]

@laoyuan ...你让我心碎。。。的无以复加

[kzzhr]

转成字符串的本质也是遍历，如果这个也不可以的话，问题就转换成了薛定谔的猫：如何在不查看数组元素的办法猜里面是啥样

[bramblex]

每一种方法都在遍历啊卧槽……

[BooksE]

@procen424 赞同,检查每一个位.不过不知道出题人到底是啥意思

[latyas]

大小都没超过128，7个8bit的数位， 53->00110101
00110101001101010011010100110101001101010011010100110101
XOR 原始数组

如果53在其中，则会有序数为8的整数倍开始的连续的8个0
所以目标是是检测是否有这样的 00000000

对XOR结果的第一第二字节 和第四第五字节 取AND操作，得到的结果和 （11111111第三字节位码） 取AND操作，得到一个结果a

if !( a & b0000000011111111) || !(a & b1111111100000000)

则认为53在原始数组中， 瞎说的 不知道对不对
好像没遍历？

[wy315700]

@sirgod
@laoyuan
不遍历怎么乘起来

[yiplee]

将 Array 转为 Set ,再记下集合里面元素的个数，然后添加 53 进去。如果集合里面元素个数多了一个，那么 53 不在里面；如果保持不变，那么在里面。（我瞎扯的）

[liuchang0812]

难道没人知道 bloom filter？