引言
数据结构和算法对于程序员来说相当重要,我最近打算学习这一门课程,并以博客的形式记录自己的学习过程和心得,目前暂时从两本书入手,一本是《大话数据结构》,一本书《算法图解》,我先从《算法图解》,这本手开始学习吧~。如果你最近也在学习,可以关注一起学习,一起交流哦~
二分查找
先从一个问题思考,假设我们现在查找英语字典里的一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】
一起不断探索自我、走出迷茫、找到热爱,希望和你成为朋友,一起成长~