您好,匿名用户
随意问技术百科期待您的加入

二分查找算法及变种的编码实现

0 投票

二分查找问题是比较经典而且面试中常考的问题,实现起来还是容易出问题,能够过关的不多,请问实现一个二分查找有哪些容易错的地方(比如小数的处理、数据相加的范围等)?

变种一:(多个公司的面试都喜欢出)如果有序序列发生偏移即把序列的后面一部分截取放在前面,比如:

11 13 1 2 4 7 9

此时再给定一个数,查找其在序列中是否存在(返回其位置),请问如何实现?

变种二:同上题描述,找出序列中最小元素位置。

变种三:给定任意一个序列,找出其中的一个谷/峰,谷的定义为两边的数均大于某个数。

请问面试中还遇到过哪些二分查找的变种?

用户头像 提问 2014年 5月14日 @ Hecarim 上等兵 (361 威望)
分享到:

1个回答

0 投票
  1. 对于输入的所有单词,使用排序算法使得所有单词按照字典序排列,然后用BS算法找到给定的单词的下标。
  2. 在给定的字符串序列中(按照字典序排列好的)存在一些空串,请你找出给定字符串的位置,不在里面返回 -1.
  3. 在一个排序好的数组中,有一些元素是重复的。 我们写一个函数,对给定的数,我们返回这个数出现的次数。
  4. 在行列排序的矩阵中里面需找某个元素,例如如下输入:
1 5 7 10
2 6 8 15
4 9 11 16
12 13 19 21

输入满足按行来看,是递增排序,按列也是递增排序,现在要是否存在某个元素。

用户头像 回复 2014年 5月14日 @ Varus 上等兵 (281 威望)
提一个问题:

相关问题

+3 投票
1 回复 76 阅读
0 投票
1 回复 32 阅读
0 投票
1 回复 1 阅读
0 投票
1 回复 7 阅读
用户头像 提问 2014年 5月14日 @ Ahri 上等兵 (292 威望)
+1 投票
0 回复 25 阅读

欢迎来到随意问技术百科, 这是一个面向专业开发者的IT问答网站,提供途径助开发者查找IT技术方案,解决程序bug和网站运维难题等。
温馨提示:本网站禁止用户发布与IT技术无关的、粗浅的、毫无意义的或者违法国家法规的等不合理内容,谢谢支持。

欢迎访问随意问技术百科,为了给您提供更好的服务,请及时反馈您的意见。
...