二分查找问题是比较经典而且面试中常考的问题，实现起来还是容易出问题，能够过关的不多，请问实现一个二分查找有哪些容易错的地方（比如小数的处理、数据相加的范围等）？
变种一：（多个公司的面试都喜欢出）如果有序序列发生偏移即把序列的后面一部分截取放在前面，比如：
11 13 1 2 4 7 9
此时再给定一个数，查找其在序列中是否存在（返回其位置），请问如何实现？
变种二：同上题描述，找出序列中最小元素位置。
变种三：给定任意一个序列，找出其中的一个谷/峰，谷的定义为两边的数均大于某个数。
请问面试中还遇到过哪些二分查找的变种？
个人总结的几个变种（只是为了描述算法本身，为了简单不考虑越界等等异常情况），欢迎补充。
/*
二分查找的前提是数组有序
二分查找的时间复杂度：O（lgn）
以下列出二分查找的三种动机：
1、查找满足条件的关键字的位置
2、查找满足条件的最小位置
3、查找满足条件的最大位置
找不到返回-1,找到了则返回位置
*/
//动机1(原始模型)：查找满足条件的关键字的位置
int BinarySearch(int *a,int l,int r)
{
int m;
while(l<=r)
{
m=(l+r)/2;
if(a[m]==key)
return m;
if(a[m]>key)
r=m-1;
else
l=m+1;
}
return-1;
}
//动机2：找满足条件的最小位置
int BinarySearch(int *a,int l,int r)
{
int m,ans=-1;
while(l<=r)
{
m=(l+r)/2;
//满足条件
if(ok())
ans=m,r=m-1;
else
l=m+1;
}
return ans;
}
//动机3：找满足条件的最大位置
int BinarySearch(int *a,int l,int r)
{
int m,ans=-1;
while(l<=r)
{
m=(l+r)/2;
//满足条件
if(ok())
ans=m,l=m+1;
else
r=m-1;
}
return ans;
}
//动机2、3十分相似,举一种常用情况：找小于等于某数的最大位置
int BinarySearch(int *a,int l,int r,int key)
{
int m,ans=-1;
while(l<=r)
{
m=(l+r)/2;
if(key>=a[m])
ans=m,l=m+1;
else
r=m-1;
}
return ans;
}
//变型1：找满足条件的最小数(double)
double BinarySearch(double l,double r)
{
double m,ans;
//保留n位小数就让精度为n+1位,比如要求保留3位小数就让精度为4位
while(r-l>=0.0001)
{
m=(l+r)*0.5;
if(ok())
ans=m,r=m;
else
l=m;
}
return ans;
}
说下第三个
要用三分法
记 l , m , r 分别为左端点、中端点、右端点。f(x) 为在x点的函数的值
取 lm = (l + m ） / 2 , rm = (m + r) / 2 ;
然后 比较 f(lm) f(rm)的关系 ， 相应的更新l , m , r 就可以了
- 对于输入的所有单词，使用排序算法使得所有单词按照字典序排列，然后用BS算法找到给定的单词的下标。
- 在给定的字符串序列中（按照字典序排列好的）存在一些空串，请你找出给定字符串的位置，不在里面返回 -1.
- 在一个排序好的数组中，有一些元素是重复的。 我们写一个函数，对给定的数，我们返回这个数出现的次数。
- 在行列排序的矩阵中里面需找某个元素，例如如下输入：
1 5 7 10
2 6 8 15
4 9 11 16
12 13 19 21
输入满足按行来看，是递增排序，按列也是递增排序，现在要是否存在某个元素。