二分查找
排序完后利用二分查找可以高效完成数据的查找，二分查找只适用于有序数列，时间复杂度为O(log(n))。
其采用折中法，尽量找中间数进行判断，这是最高效的一种查找方法
来看具体代码：
/*************************************************************************
> File Name: 1166.cpp
> Author:chudongfang
> Mail:1149669942@qq.com
> Created Time: 2016年06月15日 星期三 16时43分32秒
************************************************************************/
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
using namespace std;
typedef long long ll;
void Q_sort(int a[],int n);
int my_bsearch(int a[],int x,int y,int v);
int my_lower_bound(int a[],int x,int y,int v);
int my_upper_bound(int a[],int x,int y,int v);
int main(int argc,char *argv[])
{
int a[100]={1,2,3,3,5,3};
int n=6;
Q_sort(a,n);
for(int i=0;i<n;i++)
printf("%d ",a[i]);
printf("\n%d %d %d",my_bsearch(a,0,n-1,3),my_lower_bound(a,0,n-1,3),my_upper_bound(a,0,n-1,3));
return 0;
}
//先利用快速排序，进行排序。
void Q_sort(int a[],int n)
{
int key=a[0];//利用key进行划分
int i=0,j=n-1;
if(n<=1) return ;
else
{
while(i!=j)
{
for(;i<j;j--)
if(a[j]<key)
{
a[i]=a[j];
break;
}
for(;i<j;i++)
if(a[i]>key)
{
a[j]=a[i];
break;
}
if(i==j) a[i]=key;
}
Q_sort(a,i);//递归求解
Q_sort(a+i+1,n-i-1);
//由于其已经有序，就不用再进行合并。
}
}
//在有序数列中寻找元素。
int my_bsearch(int a[],int x,int y,int v)
{
int m;
while(x<y)//当x==y时会退出
{
m=x+(y-x)/2;
if(a[m]==v) return m;//找到相应数，返回值
else if(a[m]>v) y=m;
else x=m+1;
}
return -1;//找不到，返回-1
}
//如果要寻找的元素有多个，着他们必定连续，则该函数寻找其最前面下标
int my_lower_bound(int a[],int x,int y,int v)
{
int m;
while(x<y)
{
m=x+(y-x)/2;
if(a[m]>=v) y=m;//等于号，就显示了当a[y]==v其会继续改变，而x不会。
else x=m+1;
}
return x;
}
//该函数返回其最后下标
int my_upper_bound(int a[],int x,int y,int v)
{
int m;
while(x<y)//与上者类似
{
m=x+(y-x)/2;
if(a[v]<=v) x=m+1;
else y=m;
}
return y;
}