使用循环与递归的二分查找 博客分类： 数据结构与算法 算法

二分查找

简述：

二分查找主要用于在有序数组中查找某个数据项，具有查找速度快的优点，其算法所花时间与数据项的个数的比可用大O表示为O(logN)来表示。数据项的个数越多，越能反应出其优点。

循环

Code：

    Long[] array; //表示一个Long型的数组引用, 需要初始化
    int nElements; //表示数组中数据项的个数, 需要初始化
    int compareTimes = 0; //定义比较次数

    public int find(long searchKey) {
        int lowerBound = 0; //表示下界
        int upperBound = nElements - 1; //表示上界
        int curIn;

        while(true) {
            compareTimes++;//循环一次,比较次数加1
            curIn = (lowerBound + upperBound) / 2;
            if (array[curIn] == searchKey) {
                return curIn;  //找到所要查找的数据，位于array[curIn]
            } else if (lowerBound > upperBound) {
                return nElements; //范围不存在, 返回数据项的个数表示找不到数据
            } else {
                if (array[curIn] > searchKey) { //查找数据位于array[lowerBound] - array[curIn]之间
                    upperBound = curIn - 1; //此时上界减1, 因为之前已经判断过array[curIn]和searchKey的值是否相等
                } else { //查找数据位于array[curIn] - array[upperBound]之间
                    lowerBound = curIn + 1; //此时下界加1
                }
            }
        }
    }

查找次数计算：
通过求以2为底，范围N的对数可得到二分查找所需要的比较次数。
比如范围为10，那么4次比较完全可以查找到任何该范围内的数，实际上可以涵盖范围为16的查找。2的3次方 < 10 < 2的4次方

使用二分查找来插入数据项

虽然比较次数变小了，但是数据项的移动仍然与线性插入一样，O(N).

public void insertByBinarySearch(long value) {
        int lowerBound = 0; //表示下界
        int upperBound = nElements - 1; //表示上界
        int curIn;

        while (true) {
            curIn = (lowerBound + upperBound) /2;
            //如果value的值和array[curIn]相等, 则插入到curIn+1的位置,原curIn右边的数据项右移.
            if (array[curIn] == value) {
                for (int k = nElements - 1; k > curIn; k--) {
                    array[k+1] = array[k];
                }
                array[curIn+1] = value;
                nElements++;
                compareNums++; //比较次数
                break;
            } else if (array[curIn] > value) { //value的值小于array[curIn].
                if (array[curIn-1] < value) { //value的值位于array[curIn-1]和array[curIn]之间.
                    for (int k = nElements; k > curIn; k--) {//curIn及其后续的所有数据项依次右移
                        array[k] = array[k-1];
                    }
                    array[curIn] = value; //在curIn位置插入value
                    nElements++;//数据项个数+1
                    break;
                } else { //继续2分查找
                    upperBound = curIn -1;
                }
                compareNums++; //比较次数
            } else { //value的值大于array[curIn].
                if (value < array[curIn+1]) { //value的值位于array[curIn]和array[curIn+1]之间.
                    for (int k = nElements - 1; k > curIn; k--) { //curIn+1及其后续的所有数据项依次右移
                        array[k+1] = array[k];
                    }
                    array[curIn+1] = value;//在curIn位置插入value
                    nElements++;//数据项个数+1
                    break;
                } else { //继续2分查找
                    lowerBound = curIn + 1;
                }
                compareNums++;  //比较次数
            }
        }
    }

递归

通常，递归的速度要比循环慢一些，但是递归的代码要简洁很多。

    //对外提供的public方法, 调用private recFind()方法
    public int find(long searchKey) {
        return recFind(searchKey, 0, nElements - 1);
    }

    private int recFind(long searchKey, int lowerBound, int upperBound) {
        int curIn;
        curIn = (lowerBound + upperBound) / 2;

        if (a[curIn] == searchKey)
            return curIn;
        else if (lowerBound > upperBound)
            return nElements;
        else {
            if (a[curIn] < searchKey)
                return recFind(searchKey, curIn + 1, upperBound);
            else {
                return recFind(searchKey, lowerBound, curIn - 1);
            }
        }
    }