折半查找法

//折半查找法，要求有序序列，默認由小到大
#include <iostream>

using namespace std;
//普通方法
int BinSearch2(int *searchTable,int key,int len)
{
    // 最低位置索引low、最高位置索引high、中間位置索引mid
    // 中間位置的可能情況
    // len為奇數時，mid 為正中間位置 mid的左側和右側用于同樣數目的元素
    // len為偶數時，mid為正中間往左的那一個元素   正中間為小數，正中間往左的那一個位置才是(Low+High)/2
    // low與high的關系
    // 正常情況下low<high
    // low==high時，僅剩下最后一個需要判斷的元素，此元素可能與key相同，也可能不同
    // low>high 未找到與key相同的元素
    int low=0;
    int high=len-1;
    int mid;

    while(low<=high){
        mid=(low+high)/2;
        //找到與key相等的一個元素位置
        if(searchTable[mid]==key)
            return mid;
        if (searchTable[mid]>key)
            high=mid-1;
        else
            low=mid+1;
    }
    return -1;
}
//遞歸方法
int BinSearch3(int *searchTable,int key,int low,int high)
{
    if(low>high)
        return 0;//查找失敗
    int mid=(low+high)/2;
    if(searchTable[mid]==key)
        return mid;//查找成功
    if(searchTable[mid]>key)
        return BinSearch3(searchTable,key,low,mid-1);//左查找
    else
        return BinSearch3(searchTable,key,mid+1,high);//右查找
}
int main(int argc, char *argv[])
{
    int Array[15]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
    cout<<"3的位置是："<<BinSearch2(Array,8,15)<<endl;
    cout<<"3的位置是："<<BinSearch3(Array,8,1,15)<<endl;
    return 0;
}