算法讲解--二分查找、大O表示法

首先，祝各位大朋友和小朋友6。1 快乐哈，happy~

从今天起会陆续更新算法相关的笔记，记录一下自己学习《算法图解》的笔记，欢迎多多指教。

二分查找

二分查找是一种算法，其输入是一个有序的元素列表（必须有序，稍后会做解释）if 查找的元素包含在列表中，二分查找返回其位置，else return null;
exp: 你从电话簿中找姓q的人，可以从头开始找，傻呀你，为啥不从中间开始呢？？？因为你知道q位于电话簿中间位置。
exp: 从1~100中猜一个数字,目标最少的次数猜到该数字。 最佳方式从50开始猜。这样就排除了一半。看到这里，二分查找的精髓就展现了，没错，那就是每次都将余下的数字排除一半哈。
为啥要有序的列表呢？
because 仅当列表有序时，二分查找才有用。
exp: 电话簿的名字是按照字母排序的 ABCDEFG…,因此可以使用二分查找来查找名字。if not 按照顺序排列。结果就如何呢，xixi

大O表示法

大O表示法是一种特殊的表示法，指出了算法的速度有多快。
exp:假设列表包含n个元素，简单查找需要检查每个元素，因此需要执行n 词操作。此时，使用大O表示法，这个运行时间为O（n）。-------大O表示法指的并非以秒为单位的速度。大O表示法让你能够比较操作数，它指出了算法运行时间的增速哈。
exp:为检查长度为n的列表，二分查找需要执行log n 次操作，使用大O表示法，这个运行时间为O(log n)
注意哈：大O表示法指出了最糟糕情况下的运行时间
exp: 电话簿找人最佳情况下1次就找到了，最早情况下n次才能找到。对应运行时间O(n)

二分查找核心代码

function binary_search(list,number){
   low =0;   //下标
   high=list.length-1;
   while (low <high) {
       mid = (low+high)/2;
       guss=list[mid]；   
       if(guess  == number) {
            return mid;
	   }
	   if(guess > number) {
           high =mid -1;
       }else {
          low=mid+1;
      }
   }
   return None;
}

小结

1、二分查找速度比简单查找快
2、O(logn)比O(n) 快，需要搜索的元素越多，前者比后者就快的越多。
3、算法运行时间不以秒为单位
4、算法运行时间以用O表示法表示。
5、算法运行时间以增速角度度量的。

扩展

O(log n) 也叫对数时间   exp  二分查找
O(n) 也叫线性时间   exp  简单查找  for(int i=0;i<n;i++)
O(n*log n)    exp   快速排序 [每一层排序n 一共logn层 后续会讲解]
O(n2)    exp  选择排序----一种较慢的排序算法
O(n!)   旅行商问题