首先问大家一个问题:
小明心里默想一个数字(在1–100中),让大红去猜,小明会告诉大红她猜的数字是大了、小了或者猜对了。
如果说大红从1往上一个一个猜,那么每次能排除一个数字。那小明要是猜的100,大红就要猜100次。这就是简单查找的工作原理。
我们现在换一种方法,下面是他们之间的对话。
——大红:“50”
——小明:“小了”
——大红:“75”
——小明:“大了”
——大红:“63”(50和75中间的数字)
——小明:“大了”
——大红:“57”(50和63之间的数字)
——小明:“你终于猜对了”
这就是二分查找的工作原理。
二分查找是一种算法,其输入是一个有序的元素列表。如果要查找的元素