关于递归与二分查找技术

简单的说，递归就是函数自己调用自己。在数据结构里面会经常使用递归，因为递归代码比较简洁优雅，易懂。

编写递归程序时主要注意三点

（1）递归总有一个最简单的情况，方法的第一条语句总是包含return的条件语句

（2）递归调用总是去尝试解决一个规模更小的子问题，这样递归才能收敛到最简单的情况。在下面代码中，第四个参数和第三个参数的差值一直在缩小

（3）递归调用的父问题和尝试解决的子问题之间不应该有交集。在如下代码中，两个子问题，各自操作的数组部分是不同的

下面是二分法查找的递归实现和非递归实现；

特别注意一点，二分查找技术，是针对有序的数组和顺序表，不能忘记前提

//使用递归实现二分法查找,同时使用函数重载
    public static int rank(int key,int a[])
    {
        return rank( key,a,0,a.length-1);
    }
    public static int rank(int key,int[]a,int lo,int hi)
    {
        if(lo>hi)
            return -1;
        int mid=lo+(hi-lo)/2;
        if(key<a[mid])
            return rank(key,a,lo,mid-1);
        else if(key>a[mid])
            return rank(key,a,mid+1,hi);
        else
            return mid;
    }

二分查找算法的非递归实现

public static int BinarySearch(int arr[],int key)
{
    int low,high,mid;
    low=0;
    high=arr.length-1;
    while(low<=high)
    {
        mid=low+(high-low)/2;
        if(key<arr[mid])
            high=mid-1;
        else if(key>arr[mid])
            low=mid+1;
        else
            return mid;
    }
    return 0;
}

关于递归与二分查找技术,布布扣,bubuko.com

关于递归与二分查找技术

原文：http://liuzhangheng.blog.51cto.com/8792220/1406875