二分查找的递归与非递归实现

对于一个排好序的数组，用二分查找会更快速。

算法步骤：

1. 先取这个数组的中间值，以此为界将数组分为两个小数组。
2. 如果中间值比查找值大，那么说明查找值在前面的小数组里；否则在后面的小数组里。那么我们只需要移动下标就可以完成这个划分数组的操作。
3. 这样在查找时，每个当前的数组的查找过程都是一样的（因为每一步在这个当前的数组进行查找的操作一样，即取中间值，比较，改变传入的下标），只需要满足条件：low <= high，就可以一直查找，直到找到或找不到。

非递归的实现：

int Binary_Search(int m[] , int key , int length){//length为数组长度
    int low = 0 ;
    int high = length - 1 ;
    int mid ;
    while(low <= high){
        mid = (low + high) / 2 ; 
        if(m[mid] == key) return mid ;
        else if(m[mid] > key) high = mid - 1 ;
        else low = mid + 1 ;
    }
    return -1 ;
}

递归的实现：

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

完整代码及测试样例：

#include<iostream>
using namespace std ;

/*非递归形式*/
int Binary_Search(int m[] , int key , int length){
    int low = 0 ;
    int high = length - 1 ;
    int mid ;
    while(low <= high){
        mid = (low + high) / 2 ; 
        if(m[mid] == key) return mid ;
        else if(m[mid] > key) high = mid - 1 ;
        else low = mid + 1 ;
    }
    return -1 ;
}

/*递归形式*/
int Binary_Search2(int m[] , int key , int low , int high){
    int mid = (low + high) / 2 ;
    if(low > high) return -1 ;
    if(m[mid] == key) return mid ;
    else if(m[mid] > key) return Binary_Search2(m , key , low , mid - 1) ;
    else return Binary_Search2(m , key , mid + 1 , high) ;
}

void test(){
    int m[8] = {1 , 4 , 5 , 7 , 9 , 10 , 20 , 32} ;
    cout << Binary_Search(m , 9 , 8) << endl ;
    cout << Binary_Search2(m , 32 , 0 , 7) ;  //返回的是下标
}

int main(){
    test() ;
    return 0 ;
}