本文档精炼《算法图解》的内容，用于自我总结，分享讲解。
image.png

基本概念

算法：算法是一组完成任务的指令。任何代码片段都可以视为算法，但是我们只讨论有趣的部分。

对数：对数运算是幂运算的逆运算。

大O表示法：
1.指出算法的速度有多快。
2.指最糟情况下的运行时间。
3.算法的运行时间以不同速度增加，大O表示法可以比较操作数，指出了算法运行时间的增速。

二分查找

原理：随便想1～100的数字，从50开始猜，小了则猜75，以此类推直到找到。

  1.  function binary_search(arr, key) {
  2.    let low = 0,
  3.        high = arr.length - 1;
  4.    while(low <= high){
  5.      let mid = parseInt((high + low) / 2);
  6.      if(key == arr[mid]){
  7.        return  mid;
  8.      }else if(key > arr[mid]){
  9.        low = mid + 1;
  10.      }else if(key < arr[mid]){
  11.        high = mid -1;
  12.      }else{
  13.        return -1;
  14.      }
  15.    }
  16.  };
  17. let arr = [1,2,3,4,5,6,7,8,9,10,11,23,44,86];
  18. let result = binary_search(arr,10);
  19. console.log(result); // 9 返回目标元素的索引值

使用场景：
查找字典中的一个单词，该字典包含240’000个单词。
如果查找单子位于字典末尾，使用简单查找需要240’000步，使用二分查找只需要17步。
简查查找 O(n)
二分查找 O(log n) = O(log2 n)