折半查找的递归和非递归方法

折半查找,又称作二叉搜索,是面试时经常问到的算法问题,今天我们来看一下它的非递归和递归方法.

在有序表中，把待查找数据值与查找范围的中间元素值进行比较，会有三种情况出现：
1） 待查找数据值与中间元素值正好相等，则放回中间元素值的索引。
2） 待查找数据值比中间元素值小，则以整个查找范围的前半部分作为新的查找范围，执行1），直到找到相等的值。
3） 待查找数据值比中间元素值大，则以整个查找范围的后半部分作为新的查找范围，执行1），直到找到相等的值
4） 如果最后找不到相等的值，则返回错误提示信息。

按照二叉树来理解：中间值为二叉树的根，前半部分为左子树，后半部分为右子树。折半查找法的查找次数正好为该值所在的层数。等概率情况下，约为log2(n+1)-1

• 非递归方法

int BinTree(int Array[],int arrayLength,int key){
    int min = 0, max = arrayLength;
    int mid;
    while (min <= max) {
        mid = (min + max) / 2;
        if (key == Array[mid]) {
            return mid;
        }
        if (key < Array[mid]) {
            max = mid-1;
        }else if(key > Array[mid]){
            min = mid+1;
        }
    }
    return -1;
}

• 递归方法

int BinTree(int Array[],int min,int max,int key){
    if(min <= max){
        int mid = (min + max) / 2;
        if (key == Array[mid]) {
            return mid;
        }else if(key < Array[mid]){
            return BinTree(Array, min, mid-1, key);
        }else if(key > Array[mid]){
            return BinTree(Array, mid+1, max, key);
        }
    }
    return -1;
}