二分查找问题是比较经典而且面试中常考的问题，实现起来还是容易出问题，能够过关的不多，请问实现一个二分查找有哪些容易错的地方（比如小数的处理、数据相加的范围等）？变种一：（多个公司的面试都喜欢出）如果有序序列发生偏移即把序列的后面一部分截取放在前面，比如：111312479此时再给定一个数，查找其在序列中是否存在（返回其位置），请问如何实现？变种二：同上题描述，找出序列中最小元素位置。变种三：给定任意一个序列，找出其中的一个谷/峰，谷的定义为两边的数均大于某个数。请问面试中还遇到过哪些二分查找的变种？
2 回答
阿晨1998
TA贡献2037条经验 获得超6个赞
对于输入的所有单词，使用排序算法使得所有单词按照字典序排列，然后用BS算法找到给定的单词的下标。在给定的字符串序列中（按照字典序排列好的）存在一些空串，请你找出给定字符串的位置，不在里面返回-1.在一个排序好的数组中，有一些元素是重复的。我们写一个函数，对给定的数，我们返回这个数出现的次数。在行列排序的矩阵中里面需找某个元素，例如如下输入：157102681549111612131921输入满足按行来看，是递增排序，按列也是递增排序，现在要是否存在某个元素。
红糖糍粑
TA贡献1815条经验 获得超6个赞
说下第三个要用三分法记l,m,r分别为左端点、中端点、右端点。f(x)为在x点的函数的值取lm=(l+m）/2,rm=(m+r)/2;然后比较f(lm) f(rm)的关系，相应的更新l,m,r就可以了
添加回答
举报
0/150
提交
取消