二分查找

什么是二分查找

又叫折半查找，是一种效率高效的查找方法

原理：将数组分为三部分，依次是中值前、中值、中值后。将要查找的值和中值比较，若小于中值则在中值前找，若大于中值则在中值后面找，等于中值时直接返回

二分查找的前提

• 必须采用顺序存储结构
• 必须按关键字大小有序排列

代码实现(递归版)

def binary_search(alist, item):
    """二分查找"""

    # 数列的长度
    n = len(alist)

    # 递归的结束条件
    if n == 0:
        return False

    # 中间值 // 整除
    mid = n // 2

    if item == alist[mid]:
        return True
    elif item < alist[mid]:
        return binary_search(alist[0:mid], item) # 注意要加return 否则最终的查找结果是None, return不具有向上的传递性
    elif item > alist[mid]:
        return binary_search(alist[mid + 1:], item) # 注意要加return 否则最终的查找结果是None

if __name__ == '__main__':
    alist = [1, 2, 3, 4, 5]
    print(binary_search(alist, 1))
    print(binary_search(alist, 6))

代码实现(非递归版)

def binary_search(alist, item):
    """二分查找"""

    # 设置起始位置 获取中间值
    start = 0
    end = (len(alist) - 1)

    while start <= end:
        # 获取中间值
        mid = (start + end) // 2

        if item == alist[mid]:
            return True
        elif item < alist[mid]:
            end = mid - 1
        elif item > alist[mid]:
            start = mid + 1

    # 没有找到想要找的数字
    return False

if __name__ == '__main__':
    alist = [1, 2, 3, 4, 5]
    print(binary_search(alist, 3)) # True
    print(binary_search(alist, 9)) # False

Java版实现(非递归版)

/*1. 定义两个变量，表示要查找的范围，默认min=0, max=最大索引
2. 循环查找，但是min <= max
3. 计算出mid的值
4. 判断mid位置的元素是否为要查找的元素，如果是直接返回对应索引
5. 如果要查找的值在mid的左半边，那么min值不变，max = mid -1, 继续下次循环查找
6. 如果要查找的值在mid的右半边，那么max值不变，min = mid + 1, 继续下次循环查找
7. 当min > max时，表示要查找的元素在数组中不存在，返回-1. */*
 public static int binarySearchForIndex(int[] arr, int number) {
        // 1. 定义查找的范围
        int min = 0;
        int max = arr.length - 1;
        // 2.循环查找 min <= max
        while(min <= max){
            // 3. 计算出中间位置mid
            int mid = (min + max) / 2;
            // mid指向的元素 > number
            if (arr[mid] > number){
                // 表示要查找的元素在左边
                max = mid - 1;
            }else if (arr[mid] < number){
                // mid指向的元素 < number
                // 表示要查找的元素在右边
                min = mid + 1;
            }else{
                // mid指向的元素 == number
                return mid;
            }
        }
        // 如果min大于了max就表示元素不存在，返回-1
        return -1;
    }

二分查找时间复杂度

最差时间复杂度：$O(lo{g}_2(n))$

最优时间复杂度：$O(1)$