折半查找

要求：序列有序

实现：采用递归和非递归两种办法都能实现。

非递归：

int bin_search(int key[],int n,int k){
    int low = 0, high = n-1, mid;
    while(low<high){
        mid = high-(high-low)/2;
        if(key[mid]==k){
            return mid;  // 查找成功，返回mid
        }else if(k>key[mid]){
            low = mid+1;  // 在后半序列中查找
        }else{
            high = mid-1;  // 在前半序列中查找
        }
    }
}

递归：

int bin_search(int key[], int low,int high, int k){
    int mid;
    if(low>high){
        return -1;
    }else{
        mid = high-(high-low)/2;
        if(key[mid]==k){
            return mid;
        }else if(k>key[mid]){
            return bin_search(key,mid+1,high,k);
        }else{
            return bin_search(key,low,mid-1,k);
        }
    }
}