紫書_第八章_高效算法設計_8.2.3——二分查找

二分查找 排序完後利用二分查找可以高效完成資料的查找，二分查找隻适用于有序數列，時間複雜度為O(log(n))。 其采用折中法，盡量找中間數進行判斷，這是最高效的一種查找方法  來看具體代碼：

/*************************************************************************
	> File Name: 1166.cpp
	> Author:chudongfang 
	> Mail:[email protected] 
	> 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;
}