感觉程序不会这么长，略微整理了一下。一共两大类情况：
假设待查找序列为x[i+1],...,x[n],x[1],...,x[i]序列长度为n，待查数值为v
情况1，二分点j落在i+1和n之间
这种情况下x[i+1]<x[j]且x[j]>x[i]
若v==x[j]，返回；
若v>x[j]，在右侧子序列查找，反之则既要在左侧子序列查找，也要在右侧子序列查找;
情况2，二分点j落在1和i之间
这种情况下x[i+1]>x[j]且x[j]<x[i]
若v==x[j]，返回；
若v<x[j]，在左侧子序列查找；反之则既要在左侧查找也要在右侧查找。
代码如下：
代码:
#include <vector>
#include <iostream>
#include <algorithm>
template<typename T>
int b_find(T& xs, int v){
if(xs.empty())
return -1000;
if(xs.size()==1)
return xs[0]==v? 0: -1000;
int offset=xs.size()/2;
if(v==xs[offset])
return offset;
T left(xs.begin(), xs.begin()+offset);
T right(xs.begin()+offset, xs.end());
int i;
if(xs.front()<xs[offset] && xs[offset]>xs.back())
if(v>xs[offset])
return b_find(left,v);
else if((i=b_find(left, v))>0)
return i;
else
return left.size()+b_find(right,v);
else //xs.front()>xs[offset] && xs[offset]<xs.back()
if(v<xs[offset])
return b_find(left, v);
else if((i=b_find(right, v))>0)
return i+left.size();
else
return b_find(left,v);
}
template<typename T>
int binary_find(T& xs, int v){
int res=b_find(xs, v);
return res<0? -1: res;
}
int main(int, char**){
const int xs[]={20, 24, 6, 7, 9, 11, 13};
std::vector<int> xsv(xs, xs+sizeof(xs)/sizeof(int));
std::cout<<binary_find(xsv, 6)<<"\n";
std::cout<<binary_find(xsv, 15)<<"\n";
}
运行结果如下：
chen@chen-PC /cygdrive/d/liuxinyu/temp/c++
$ g++ foo1.cpp
chen@chen-PC /cygdrive/d/liuxinyu/temp/c++
$ ./a
2
-1