骨骼全职店面

上周二约的今天的店面，美国小哥，人巨好，沟通很顺，准时打来，先自我介绍寒暄，然后问我会binary search吗，blabla讲一堆，
然后做题：我们重新定义一种新的二分查找法：
1. 二分的pivot是random的（普通二分法

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

问问题，结束。。。

不得不说狗家题实在太活了，各种变形，很难碰到原题，还是得多做题找感觉，面试时候不清楚及时沟通，求onsite！！！

楼主能具体一点题目么， input和require output是什么呀？没太明白， 给楼主加米，感谢

AngelSeven 发表于 2018-12-14 04:50
楼主能具体一点题目么， input和require output是什么呀？没太明白， 给楼主加米，感谢

input是一个array， 比如【4，6，5】
output就是一个int（一定能用新的二分法找到的element的个数），如果是上面的input的话就是1

这个题是很不清楚。。。

楼主能详细解释一下吗？
binary search的话这个target是什么
为什么可以return number of elements呢？

target就是一个数， # of elements就是能用新的search 的方法能找到的个数，
比如【4，6，5】， 里面总共三个element 4，5，6：

1. 我们先看用新的search的方法能不能找到 4（4就是target）  =》 结果可以 +1
2. 再看用新的search的方法能不能找到 5  =》 就不+
2. 再看用新的search的方法能不能找到 6  =》 就不+

最终发现只有4可以，就return 1

hjr01211 发表于 2018-12-29 00:51
target就是一个数， # of elements就是能用新的search 的方法能找到的个数，
比如【4，6，5】， 里面总共 ...

意思是每个这个array的element都作为target搜索一遍？然后看加不加一？
为什么4 可以找到，5找不到？
如果pivot不是二分而是random的话不是结果是unpredictable的吗？
4也不一定一定能够找到吧？

1. 是的
2. 找5的时候，pivot有可能random到6， 然后就往左找了，范围缩小到6左边【4】，永远不能找到5了
3. 对，，结果不能全部predict，但有部分的element可以100%确认能找到，就是题目本意
4. 找4的话：
     a. random到4  -》 找到了
     b.random到6， 根据二分方法往左找，list变成【4】 -》 找到了
     c. random到5， 根据二分方法往左找， list变成【4， 6】 -》同理也能找到