猜数字
现有两个玩家，分别为玩家A和玩家B；
玩家A从一个范围中选择一个数（例如从 [1,1000] 中选择了352）
让玩家B猜玩家A选择的数
若玩家B猜的数字x小于352，说明x<352<=1000,应当在 [x+1,1000]中继续猜；
若玩家B猜的数字x大于352，说明1<=352<x,应当在 [1,x-1] 中继续猜。
显然，每次选择当前范围的中间数去猜，就能尽可能快的逼近正确的数字，并最终将其猜出来。
由此，引申出的经典问题：如何在一个严格递增序列A中找出给定的数x。
最直接的办法是：线性扫描序列中的所有元素
如果当前元素恰好为x，则表明查找成功；
-
如果扫描完整个序列都没有发现给定的数x,则表明查找失败，说明序列中不存在数x。
顺序查找的时间复杂为O(n)(其中n为序列元素个数)，
二分查找是基于有序序列的查找算法，该算法一开始令 [left,right]为整个序列的下标区间，然后每次测试当前 [left,right]的中间位置 mid = (left+right)/2, 判断 A[mid]与与查询的元素x的大小。
-
如果 A[mid]==x,说明查找成功，退出查询。
image-20210419215233629.png
- 如果 A[mid]>x,说明元素x在mid位置的左边，因此往左子区间[left,mid-1]继续查找。
image-20210419215442480.png
- 如果 A[mid]<x,说明元素x在mid位置的右边，因此往右子区间 [mid+1,right]继续查找。
image-20210419215648819.png
二分查找：每一步都可以去除当前区间的一半元素，因此其时间复杂度是O(logn)。
