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

Question

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

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

11 13 1 2 4 7 9

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

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

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

Answer 1

对于输入的所有单词，使用排序算法使得所有单词按照字典序排列，然后用BS算法找到给定的单词的下标。在给定的字符串序列中（按照字典序排列好的）存在一些空串，请你找出给定字符串的位置，不在里面返回 -1.在一个排序好的数组中，有一些元素是重复的。 我们写一个函数，对给定的数，我们返回这个数出现的次数。在行列排序的矩阵中里面需找某个元素，例如如下输入：1 5 7 102 6 8 154 9 11 1612 13 19 21输入满足按行来看，是递增排序，按列也是递增排序，现在要是否存在某个元素。

Answer 2

说下第三个要用三分法记 l , m , r 分别为左端点、中端点、右端点。f(x) 为在x点的函数的值取 lm = (l + m ） / 2 , rm = (m + r) / 2 ;然后 比较 f(lm)　f(rm)的关系 ， 相应的更新l , m , r 就可以了

Answer 3

个人总结的几个变种（只是为了描述算法本身，为了简单不考虑越界等等异常情况），欢迎补充。/*&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;二分查找的前提是数组有序 &nbsp;&nbsp;&nbsp;&nbsp;二分查找的时间复杂度：O（lgn） &nbsp;&nbsp;&nbsp;&nbsp;以下列出二分查找的三种动机： &nbsp;&nbsp;&nbsp;&nbsp;1、查找满足条件的关键字的位置 &nbsp;&nbsp;&nbsp;&nbsp;2、查找满足条件的最小位置 &nbsp;&nbsp;&nbsp;&nbsp;3、查找满足条件的最大位置 &nbsp;&nbsp;&nbsp;&nbsp;找不到返回-1,找到了则返回位置 *///动机1(原始模型)：查找满足条件的关键字的位置int&nbsp;BinarySearch(int&nbsp;*a,int&nbsp;l,int&nbsp;r){&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;m;&nbsp;&nbsp;&nbsp;&nbsp;while(l<=r) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;m=(l+r)/2;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(a[m]==key) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;m;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(a[m]>key) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;r=m-1;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;l=m+1; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;return-1; }//动机2：找满足条件的最小位置int&nbsp;BinarySearch(int&nbsp;*a,int&nbsp;l,int&nbsp;r){&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;m,ans=-1;&nbsp;&nbsp;&nbsp;&nbsp;while(l<=r) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;m=(l+r)/2;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//满足条件 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(ok()) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ans=m,r=m-1;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;l=m+1; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;ans; }//动机3：找满足条件的最大位置int&nbsp;BinarySearch(int&nbsp;*a,int&nbsp;l,int&nbsp;r){&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;m,ans=-1;&nbsp;&nbsp;&nbsp;&nbsp;while(l<=r) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;m=(l+r)/2;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//满足条件 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(ok()) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ans=m,l=m+1;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;r=m-1; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;ans; }//动机2、3十分相似,举一种常用情况：找小于等于某数的最大位置int&nbsp;BinarySearch(int&nbsp;*a,int&nbsp;l,int&nbsp;r,int&nbsp;key){&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;m,ans=-1;&nbsp;&nbsp;&nbsp;&nbsp;while(l<=r) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;m=(l+r)/2;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(key>=a[m]) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ans=m,l=m+1;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;r=m-1; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;ans; }//变型1：找满足条件的最小数(double)double&nbsp;BinarySearch(double&nbsp;l,double&nbsp;r){ &nbsp;&nbsp;&nbsp;&nbsp;double&nbsp;m,ans;&nbsp;&nbsp;&nbsp;&nbsp;//保留n位小数就让精度为n+1位,比如要求保留3位小数就让精度为4位 &nbsp;&nbsp;&nbsp;&nbsp;while(r-l>=0.0001) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;m=(l+r)*0.5;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(ok()) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ans=m,r=m;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;l=m; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;ans; }