引言
数据结构和算法对于程序员来说相当重要，我最近打算学习这一门课程，并以博客的形式记录自己的学习过程和心得，目前暂时从两本书入手，一本是《大话数据结构》，一本书《算法图解》，我先从《算法图解》，这本手开始学习吧~。如果你最近也在学习，可以关注一起学习，一起交流哦~
二分查找
先从一个问题思考，假设我们现在查找英语字典里的一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; } 执行结果 book@book-virtual-machine:~/cpp$ ./test times =4 The target at 9
程序执行查找4次，找到120在数组arr[9].
练习题
假设有一个包含128个名字的有序列表，你要使用二分查找在其中查找一个名字，请 问最多需要几步才能找到？
log(2)128=7 7次
上面列表的长度翻倍后，最多需要几步？
8步
大O表示法
算法的运行时间以不同的速度增加
| 简单查找 | 二分查找 | |
| 100个元素 | 100ms | 1ms |
| 10000个元素 | 10s | 14ms |
| 1000000000个元素 | 11天 | 32ms |
① 仅知道算法需要多长时间才能运行完毕还不够，还需知道运行时间如何随列表增长而增加。② 大O表示算法的运行速度。它的单位不是秒，而是操作数。比如说简单查找一个含n个元素的列表，需要执行n次操作。而二分查找需要执行log（2）N次。
大O表示法指出在最糟糕的情况下的运行时间
简单查找的运行时间总是为O(n)。查找Adit时，一次就找到了，这是最佳的情形，但大O表示法说的是最糟的情形。因此，你可以说，在最糟情况下，必须查看电话簿中的每个条目，对应的运行时间为O(n)。这是一个保证——你知道简单查找的运行时间不可能超过O(n)。
一些常见的大O运行时间
- O(log n)，也叫对数时间，这样的算法包括二分查找。
- O(n)，也叫线性时间，这样的算法包括简单查找。
- O(n * log n)，这样的算法包括第4章将介绍的快速排序—— 一种速度较快的排序算法。
- O(n2)，这样的算法包括第2章将介绍的选择排序—— 一种速度较慢的排序算法。
- O(n!)，这样的算法包括接下来将介绍的旅行商问题的解决方案—— 一种非常慢的算法。
小结
1. 二分查找的速度比简单查找快得多；
2. O(log n)比O(n)快。需要搜索的元素越多, 前者比后者就快得越多；
3. 算法运行时间并不以秒为单位；
4. 算法运行时间是从其增速的角度度量的；
5. 算法运行时间用大O表示法表示；
号主：一枚机械专业本科生，经历了转行，从外包逆袭到芯片原厂的Linux驱动开发工程师，深入操作系统的世界，贯彻终身学习、终身成长的理念。平时喜欢折腾，寒冬之下，抱团取暖，期待你来一起探讨技术、搞自媒体副业，程序员接单和投资理财。【对了，不定期送闲置开发板、书籍、键盘等等】。
如果你想了解我的转行经验，欢迎找我交流~gongzhong号【哆哆jarvis】
一起不断探索自我、走出迷茫、找到热爱，希望和你成为朋友，一起成长~
