算法原理

二分查找也称折半查找(Binary Search)，它是一种效率较高的查找方法。折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

二分查找的思想：在一个长度为n的有序数组中查找值等于m的元素位置，先取数组中间位置 mid 的元素与其相比。如果值等于 m 则返回 mid 值，小于 m 则在数组 0 至 mid-1 区间上按照此方法继续比较查找，大于 m 则在数组 mid + 1 至 n 区间上按照此方法继续比较查找。

时间复杂度

假设总共有n个元素，每次查找的区间大小就是n，n/2，n/4，…，n/2^k（操作元素的剩余个数），其中k就是循环的次数。
由于 n/2^k 取整后>=1，即令n/2^k=1
可得k=log2n（是以2为底，n的对数），所以时间复杂度表示为O(logn)

空间复杂度

二分查找占用空间非常小，额外使用了几个临时变量如left、right、mid，因此其空间复杂度为O(1)

动图演示

示例: 从一组有序数组[1,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59]中查询值为37的索引下标

演示.gif

代码实现

二分查找非递归方式代码：

/**
 * 二分查找(非递归方式)
 *
 * @param arr   有序数组
 * @param num   查找元素值
 * @return boolean
 */
public static int find(int[] arr, int num) {
    if (arr == null || arr.length == 0) {
        return -1;
    }

    int left = 0;
    int right = arr.length - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] == num) {
            return mid;
        } else if (arr[mid] < num) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;
}

二分查找递归方式代码：

/**
 * 二分查找(递归方式)
 *
 * @param arr   有序数组
 * @param num   查找元素值
 * @return boolean
 */
public static int find(int[] arr, int left, int right, int num) {
    if (arr == null || arr.length == 0 || left > right) {
        return -1;
    }

    int mid = (left + right) / 2;
    if (arr[mid] == num) {
        return mid;
    } else if (arr[mid] < num) {
        return find(arr,left + 1, right, num);
    } else {
        return find(arr,left + 1, right, num);
    }
}

测试代码：

public static void main(String[] args) {
    int[] array = new int[] {1, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59};
    System.out.println("二分查找非递归方式: " + find(array, 37));
    System.out.println("二分查找递归方式: " + find(array, 0, array.length - 1, 37));
}