二分查找是一种算法，其输入是一个有序的元素列表（必须有序的原因稍后解释）。如果要 查找的元素包含在列表中，二分查找返回其位置；否则返回null。

  1. def binary_search(list,item):
  2.     low = 0
  3.     high = len(list-1)
  5.     while low<=high：
  6.         mid = (low + high)/2
  7.         guess = list[mid]
  8.         if guess == item:
  9.             return mid
  10.         if guess > item
  11.             hight = mid -1
  12.         else 
  13.             low = mid + 1
  14.      return None

问题：假设有一个包含128个名字的有序列表，你要使用二分查找在其中查找一个名字，请 问最多需要几步才能找到？
Math.pow(2,7) = 128 ,7步

运行时间

  • O(log n)，也叫对数时间，这样的算法包括二分查找。
  • O(n)，也叫线性时间，这样的算法包括简单查找。
  • O(n * log n)，这样的算法包括第4章将介绍的快速排序——一种速度较快的排序算法
  • O(n2 )，这样的算法包括第2章将介绍的选择排序——一种速度较慢的排序算法。
  • O(n!)，这样的算法包括接下来将介绍的旅行商问题的解决方案——一种非常慢的算法。

js代码

  1. function binary_search(list,item){
  2.     var low = 0;
  3.     var high = list.length;
  4.        var guess ;
  5.     while (low<high){
  6.        var mid = (low+high)/2;
  7.                guess = list[mid]
  8.         if(guess === item){
  9.             return mid // 返回位置
  10.         }else if(guess > item){
  11.             high = mid - 1
  12.         }else {
  13.             low = low + 1
  14.         }
  15.     }
  16.     return `cannot find ${item} in currnet list`
  17. }