猜数字

从一个1-100的数字，随机的选择其中一个数字（假设为80），以最少的次数猜到我所选择的数字，每次猜测后，我会告诉你说的数字和我选择的数字大小关系，三种情况：大了，小了，对了。
假设你第一次从1开始猜，小了
第二次：2 小了
第三次：3 小了
……
第七十九次：79 小了
第八十次：80 对了
按照一个个数字猜测，需要80次才能猜中我选择的数字，但是如果通过折半思想，猜数字80
第一次：你从50开始猜，那么告诉你小了，就排除了接近一半的数字，因为你至少知道1-50都小了
第二次：你猜75，告诉你小了，意味着51-75都小了，这样剩下的数字又少了一半！
第三次：接下来，很明显应该猜测88，大了
第四次：然后你猜81，大了
第五次：然后你猜78 小了
第六次：然后你猜79 小了
第七次，就可以明确的告诉我，答案是80！

整体代码逻辑如下

  1. package cn.bx.datastruct;
  3. public class BinarySearch {
  4.     private static int binarySearch(int[] list,int target){
  5.         int low = 0;
  6.         int high =  list.length-1;
  7.         while (low<=high){
  8.             int mid = low+(high-low)/2;
  9.             System.out.printf("猜测数字是：%d ",list[mid]);
  10.             if (list[mid]==target){
  11.                 System.out.println("正确");
  12.                 return mid;
  13.             }else if (list[mid]<target){
  14.                 System.out.println("小了");
  15.                 low = mid+1;
  16.             }else if (list[mid]>target){
  17.                 System.out.println("大了");
  18.                 high = mid-1;
  19.             }
  20.         }
  21.         return -1;
  22.     }
  24.     public static void main(String[] args) {
  25.         int[] list = new int[100];
  26.         for (int i =1;i<=100;i++){
  27.             list [i-1] =i;
  28.         }
  29.         binarySearch(list,80);
  30.     }
  31. }

打印结果如下

  1. 猜测数字是：50 小了
  2. 猜测数字是：75 小了
  3. 猜测数字是：88 大了
  4. 猜测数字是：81 大了
  5. 猜测数字是：78 小了
  6. 猜测数字是：79 小了
  7. 猜测数字是：80 正确

概述

二分查找算法本身针对的是一个有序的数据集合，查找思想类似于分治思想。每次通过和区间中间元素的对比，将待查找的区间缩小为原来的一半，知道找到要查找的给定元素，或者区间缩小为0。二分查找的时间复杂度是O(logn)。

局限

尽管二分查找的效率很高，但是二分查找的应用场景局限性很大。
二分查找依赖的是顺序表结构， 大部分情况是数组支持下标随机访问）
二分查找针对的是有序数据，无序的数据在运用二分查找前必须需要进行排序操作，不适合有频繁插入删除擦操作的数据。
数据量太小不适合二分查找。大O表示法表示时间复杂度实则是表示的是时间开销的趋势。数据太小，不论是二分查找还是顺序遍历，查找速度都会差不多。

数据量特别大也不适合用二分查找。前面我已经提到二分查找底层依赖于数组这种数据结构，并且数据有序才可以使用二分查找。如果有几个G以上的数据，用数组存储就需要对应的连续内存空间，这显然是不切实际的。