算法学习<1>---二分查找

简介: 算法学习<1>---二分查找

引言

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

二分查找

先从一个问题思考,假设我们现在查找英语字典里的一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个名字的有序列表,你要使用二分查找在其中查找一个名字,请 问最多需要几步才能找到?

  1. log(2)128=7        7

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

  1. 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运行时间

  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表示法表示;

号主:一枚机械专业本科生,经历了转行,从外包逆袭到芯片原厂的Linux驱动开发工程师,深入操作系统的世界,贯彻终身学习、终身成长的理念。平时喜欢折腾,寒冬之下,抱团取暖,期待你来一起探讨技术、搞自媒体副业,程序员接单和投资理财。【对了,不定期送闲置开发板、书籍、键盘等等】。

如果你想了解我的转行经验,欢迎找我交流~gongzhong号【哆哆jarvis】

一起不断探索自我、走出迷茫、找到热爱,希望和你成为朋友,一起成长~

相关文章
|
17天前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
数据结构与算法系列学习之串的定义和基本操作、串的储存结构、基本操作的实现、朴素模式匹配算法、KMP算法等代码举例及图解说明;【含常见的报错问题及其对应的解决方法】你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
|
13天前
|
机器学习/深度学习 人工智能 自然语言处理
【EMNLP2024】基于多轮课程学习的大语言模型蒸馏算法 TAPIR
阿里云人工智能平台 PAI 与复旦大学王鹏教授团队合作,在自然语言处理顶级会议 EMNLP 2024 上发表论文《Distilling Instruction-following Abilities of Large Language Models with Task-aware Curriculum Planning》。
|
17天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习(8)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
17天前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之顺序表【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找等具体详解步骤以及举例说明
|
17天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
17天前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
17天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
17天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之顺序表习题精讲【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找习题精讲等具体详解步骤以及举例说明
|
17天前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构的基本概念;算法的基本概念、特性以及时间复杂度、空间复杂度等举例说明;【含常见的报错问题及其对应的解决方法】
|
17天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之王道第2.3章节之线性表精题汇总二(5)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
IKU达人之数据结构与算法系列学习×单双链表精题详解、数据结构、C++、排序算法、java 、动态规划 你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!