2019-08-23 二分查找笔记

二分查找是一种算法，其输入的是一个有序列表

示例说明二分法的工作原理：我随便想1~100个数字

    猜数，你的目标数以最少的次数猜到这个数字，你每次猜测后，我会说大了，或者小了

假设你从1开始依次往上猜：

简单查找

这是简单查找，更准确的说是傻找，每次只能排除一个数字，如果我说99，你要猜99次才能找到。

如果你每次从中间开始猜，每次可以排除一半的数字

二分法查找

java代码实现

二分法

运行时间：

一般而言，应选择效率最高的算法，来最大限度的减少运行时间或占用内存

简单查找逐个检查数字，如果列表包含100个数字，最多需猜100次，如果列表包含40亿个数字，最多需猜40亿次，最多需猜的次数与列表长度相同，这被称为线性时间。

二分法查找不同，如果列表中有100个元素，最多需要猜7次，如果列表有40亿个数字，最多需要猜32次。二分法的运行时间为对数时间（或log时间）。

如有错误，请大佬们指出，小菜鸟虚心接受