二分查找

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

适用范围：有序列表

时间复杂度：O(logn)

循环写法

/**
 * 二分查找的循环写法(升序列表)
 */
public int binarySearch(int[] array, int target) {
    int left = 0;
    int right = array.length - 1;
    while (left <= right) { // 在候选区有效时循环查找
        int middle = (left + right) / 2;
        if (array[middle] == target) {
            return middle; // 找到目标元素
        } else if (array[middle] > target) {
            // 在左侧区域查找
            left = left;
            right = middle - 1;
        } else {
            // 在右侧区域查看
            left = middle + 1;
            right = right;
        }
    }
    return -1; // 未找到目标元素
}

递归写法

/**
 * 二分查找的递归写法(升序列表)
 */
public int binarySearch(int[] array, int target, int left, int right) {
    if (left > right) {
        return -1; // 未找到目标元素
    }
    int middle = (left + right) / 2;
    if (array[middle] == target) {
        return middle; // 找到目标元素
    } else if (array[middle] > target) {
        return binarySearch(array, target, left, middle - 1); // 在左侧区域递归查找
    } else {
        return binarySearch(array, target, middle + 1, right); // 在右侧区域递归查找
    }
}