二分查找

折半查找过程可用二叉树来描述，把有序表中间位置上的结点作为树的根结点，左子表和右子表分别对应树的左子树和右子树。折半查找的过程就是走一条从根节点到被查结点的一条路径，比较的次数就是该路径中结点的个数，即，该结点在树中的层数。 深度为K的二叉树最多有2的K次方-1个结点，深度为7的二叉树最多有127个结点.

代码

public class BinarySearch {
    public static int noRecursion(int[] arr, int key, int low, int high) {
        while (low < high) {
            int mid = (low + high) >>> 1;
            int sortNum = arr[mid];
            if (key > sortNum) {
                low = mid + 1;
            } else if (key < sortNum) {
                high = mid - 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

    public static int recursion(int[] arr, int key, int low, int high) {
        int mid = (low + high) >>> 1;
        int sortNum = arr[mid];
        int res = -1;
        if (key > sortNum) {
            res = recursion(arr, key, mid + 1, high);
        } else if (key < sortNum) {
            res = recursion(arr, key, low, mid - 1);
        } else {
            return mid;
        }
        return res;
    }
}

复杂度

image.png

整个有序表可以生成深度为多少的二叉树

int TestBinSearch(int first, int end)
{
    if(first < end)
    {
        int mid = (first + end) / 2;
        int numOfLeftCmp = TestBinSearch(first, mid - 1);
        int numOfRightCmp = TestBinSearch(mid + 1, end);
        if(numOfLeftCmp > numOfRightCmp)
            return numOfLeftCmp + 1;
        else
            return numOfRightCmp + 1;
    }
    else if(first == end)
        return 1;
    else
        return 0;
}