引言

数据结构和算法对于程序员来说相当重要，我最近打算学习这一门课程，并以博客的形式记录自己的学习过程和心得，目前暂时从两本书入手，一本是《大话数据结构》，一本书《算法图解》，我先从《算法图解》，这本手开始学习吧~。如果你最近也在学习，可以关注一起学习，一起交流哦~

二分查找

先从一个问题思考，假设我们现在查找英语字典里的一K为开头的单词。如果我们从头开始翻，一直翻到K，那样太浪费时间了。通常我们都会直接翻开字典中间打开位置看看是什么字母的，如果我们翻到了J，K在J后面，那么我们继续往后翻就到了，比从头开始翻快多了。

二分查找是一种算法,其输入是一个有序的元素列表（必须有序）。如果要查找的元素包含在列表中，二分查找返回其位置，否则返回NULL。

再看一个简单的例子 如果我们现在在1到100里的数字找99，如果我们重头开始查找，需要99步 如果我们用二分查找，50->75->88->94->97->99，6次就能查找，而且在这个范围里任何数字在7次内都能查找完毕。简单查找：最多需要100步 二分查找：最多需要7步

当我们要查找的有240000元素的字典，使用二分查找，每次排除一般单词，最多只需18步。

一般而言，对于包含n个元素的列表，使用二分查找最多需要log2n步，而简单的查找需要n步。

C语言实现二分查找

 
   
   
 

  
    
    
  
#include <stdio.h>
  
    
    
  
#include <stdlib.h>
  
    
    
  
#include <string.h>
  
    
    
  


  
    
    
  
const int target = 120;
  
    
    
  
int arr[10]={0,1,2,3,4,5,6,7,8,120};
  
    
    
  


  
    
    
  
int binary_search(int *p, int target, int len)
  
    
    
  
{
  
    
    
  
 int times;//记录查找次数
  
    
    
  
 int low,high,mid;
  
    
    
  
 low = 0;//最左边元素
  
    
    
  
 high = len - 1;//最右边元素
  
    
    
  
 mid = (low+high)/2;//中间元素
  
    
    
  
 while(low <= high){//循环执行直到只有一个元素
  
    
    
  
 times++;
  
    
    
  
 mid = (low+high)/2;
  
    
    
  
 if(target < arr[mid])
  
    
    
  
 high = mid - 1;
  
    
    
  
 else if(target > arr[mid])
  
    
    
  
 low = mid + 1;
  
    
    
  
 else if(target == arr[mid]){
  
    
    
  
 printf("times = %d\n",times);
  
    
    
  
 return mid;
  
    
    
  
 }
  
    
    
  


  
    
    
  


  
    
    
  
 }
  
    
    
  
 return -1;
  
    
    
  


  
    
    
  
}
  
    
    
  
int main()
  
    
    
  
{
  
    
    
  
 int res;
  
    
    
  
 int len = sizeof(arr)/sizeof(arr[0]);
  
    
    
  
 res = binary_search(arr,120,len);
  
    
    
  
 printf("The target at %d\n",res);
  
    
    
  
 return 0;
  
    
    
  
}
 
   
   
 

 
   
   
 

  
    
    
  
执行结果
 
   
   
 

程序执行查找4次，找到120在数组arr[9].

练习题

假设有一个包含128个名字的有序列表，你要使用二分查找在其中查找一个名字，请 问最多需要几步才能找到？

 
   
   
 

  
    
    
  
log(2)128 = 7 7次
 
   
   
 

上面列表的长度翻倍后，最多需要几步？

 
   
   
 

  
    
    
  
8步
 
   
   
 

大O表示法

算法的运行时间以不同的速度增加

① 仅知道算法需要多长时间才能运行完毕还不够，还需知道运行时间如何随列表增长而增加。② 大O表示算法的运行速度。它的单位不是秒，而是操作数。比如说简单查找一个含n个元素的列表，需要执行n次操作。而二分查找需要执行log（2）N次。

大O表示法指出在最糟糕的情况下的运行时间

一些常见的大O运行时间

1. O(log n)，也叫对数时间，这样的算法包括二分查找。

2. O(n)，也叫线性时间，这样的算法包括简单查找。

3. O(n * log n)，这样的算法包括第4章将介绍的快速排序—— 一种速度较快的排序算法。

4. O(n2)，这样的算法包括第2章将介绍的选择排序—— 一种速度较慢的排序算法。

5. O(n!)，这样的算法包括接下来将介绍的旅行商问题的解决方案—— 一种非常慢的算法。

小结

1. 二分查找的速度比简单查找快得多；

2. O(log n)比O(n)快。需要搜索的元素越多, 前者比后者就快得越多；

3. 算法运行时间并不以秒为单位；

4. 算法运行时间是从其增速的角度度量的；

5. 算法运行时间用大O表示法表示；