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

Question

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

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

11 13 1 2 4 7 9

此时再给定一个数，查找其在序列中是否存在（返回其位置），请问如何实现？

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

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

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

Answer 1

1. 对于输入的所有单词，使用排序算法使得所有单词按照字典序排列，然后用BS算法找到给定的单词的下标。
2. 在给定的字符串序列中（按照字典序排列好的）存在一些空串，请你找出给定字符串的位置，不在里面返回 -1.
3. 在一个排序好的数组中，有一些元素是重复的。 我们写一个函数，对给定的数，我们返回这个数出现的次数。
4. 在行列排序的矩阵中里面需找某个元素，例如如下输入：

1 5 7 10
2 6 8 15
4 9 11 16
12 13 19 21

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