从零开始学数据结构系列之第五章《二分查找》

ops/2024/12/22 16:01:07/

文章目录

  • 二分查找
    • 原理
    • 算法步骤
    • 样例
      • 奇数情况
      • 偶数情况
  • 总代码
  • 往期回顾

二分查找

原理

​   二分查找也称折半查找，是在一组有序(升序/降序)的数据中查找一个元素，它是一种效率较高的查找方法。

​   用白话来说，就是先定位到数组中间（我们简称为 i ），然后判断要查找的数是在 i的左边（比他小），还是i右边（比他大），之后不断折半直到查找到数字，如果找不到还是返回给-1

​ 注意：线性表中存储的数据一定要是顺序的

算法步骤

  1. 查找的目标数据元素必须是有序的。没有顺序的数据，二分法就失去意义。

  2. 数据元素通常是数值型，可以比较大小。

  3. 将目标元素和查找范围的中间值做比较（如果目标元素=中间值，查找结束），将目标元素分到较大/或者较小的一组。

  4. 通过分组，可以将查找范围缩小一半。

  5. 重复第三步，直到目标元素=新的范围的中间值，查找结束。

不用去纠结数组的长度是奇数或者偶数的时候，怎么取长度的一半，以下说明，可以跳过。

样例

奇数情况

在这里插入图片描述
是奇数的情况很简单，指向中间的数字很容易理解，如果需要查找的数字为29

因为29大于中间的数字大于11，所以左边的所有数字全部排除

在这里插入图片描述

偶数情况

在这里插入图片描述
  这个时候中间的数字两边的数字数量就不一样了（刚开始学习二分法的时候我经常纠结这个问题，和另外一个长度除2得到的是最中间的数吗的问题，我相信不止我一个人纠结过……但其实这是同一个问题，每次长度除2，如果长度为奇数，得到的中间的数字两边数字数量相同，如果长度为偶数就为上图中间的数字两边的相差为 1）

  但是千万不要一直纠结中间的数字两边的数字数量不一样这个问题，因为：

两边数量不一样是一定会出现的情况
  但是这种情况并不影响我们对中间数字和目标数字大小关系的判断
    只要中间数字大于目标数字，就排除右边的
    只要中间数字小于目标数字，就排除左边的
  所以数组长度是偶数还是奇数这个真的不重要，不影响怎么排除的问题，无非是多排除一个数字或者少排除一个数字

真正影响的是中间那个数字到底该不该加入下一次的查找中，也就是边界问题

总代码

#include <stdio.h>
#include <stdlib.h>typedef struct List 
{int* data;int length;int num;
} List;List* initList(int length) 
{List* list = (List*)malloc(sizeof(List));list -> data = (int*)malloc(sizeof(int) * length);list -> length = length;list -> num = 0;return list;
}void listAdd(int data, List* list) 
{list -> data[list -> num] = data;list -> num = list -> num + 1;
}void printList(List* list) 
{int i=0;for (i = 0; i < list -> num; i++) {printf("%d ", list -> data[i]);}printf("\n");
}int binarySearch(int key, List* list) 
{int start = 0;int end = list -> num - 1;int mid;while (start <= end) {mid = (start + end) / 2;if (list -> data[mid] < key) {start = mid + 1;}else if (list -> data[mid] > key) {end = mid - 1;}elsereturn mid;}return -1;
}int binarySearchRecursion(int key, List* list, int start, int end) 
{int mid = (start + end) / 2;if (start == end) {if (list -> data[start] == key) {return start;}else {return -1;}}if (list -> data[mid] < key) {return binarySearchRecursion(key, list, mid + 1, end);}else if (list -> data[mid] > key) {return binarySearchRecursion(key, list, start, mid - 1);}else return mid;
}int main() 
{List* list = initList(9);listAdd(1, list);listAdd(2, list);listAdd(3, list);listAdd(4, list);listAdd(5, list);listAdd(6, list);listAdd(7, list);listAdd(8, list);listAdd(9, list);printList(list);printf("data %d in %d\n", 7, binarySearch(7, list));printf("data %d in %d\n", 10, binarySearch(10, list));printf("data %d in %d\n", 1, binarySearch(1, list));printf("data %d in %d\n", 3, binarySearch(3, list));printf("data %d in %d\n", 7, binarySearchRecursion(7, list, 0, list -> num - 1));printf("data %d in %d\n", 10, binarySearchRecursion(10, list, 0, list -> num - 1));printf("data %d in %d\n", 1, binarySearchRecursion(1, list, 0, list -> num - 1));printf("data %d in %d\n", 3, binarySearchRecursion(3, list, 0, list -> num - 1));return 0;
}

在这里插入图片描述

☁️ 以上就是所有内容，对大家有用的话点个关注！感谢大家！

往期回顾

1.【第一章】《线性表与顺序表》
2.【第一章】《单链表》
3.【第一章】《单链表的介绍》
4.【第一章】《单链表的基本操作》
5.【第一章】《单链表循环》
6.【第一章】《双链表》
7.【第一章】《双链表循环》
8.【第二章】《栈》
9.【第二章】《队》
10.【第二章】《字符串暴力匹配》
11.【第二章】《字符串kmp匹配》
12.【第三章】《树的基础概念》
13.【第三章】《二叉树的存储结构》
14.【第三章】《二叉树链式结构及实现1》
15.【第三章】《二叉树链式结构及实现2》
16.【第三章】《二叉树链式结构及实现3》
17.【第三章】《二叉树链式结构及实现4》
18.【第三章】《二叉树链式结构及实现5》
19.【第三章】《中序线索二叉树理论部分》
20.【第三章】《中序线索二叉树代码初始化及创树》
21.【第三章】《中序线索二叉树线索化及总代码》
22【第三章】《先序线索二叉树理论及线索化》
23【第三章】《先序线索二叉树查找及总代码》
24【第三章】《后续线索二叉树线索化理论》
25【第三章】《后续线索二叉树总代码部分》
26【第三章】《二叉排序树基础了解》
27【第三章】《二叉排序树代码部分》
28【第三章】《二叉排序树代码部分》
29【第三章】《平衡二叉树基础概念》
30【第三章】《平衡二叉树的平衡因子》
31【第三章】《平衡二叉树的旋转基础详解》
32【第三章】《平衡二叉树的旋转类型图文详解》
33【第三章】《平衡二叉树的旋转类型总结及总代码》
34【第三章】《哈夫曼树简单了解》
35【第三章】《哈夫曼树的构造方法》
36【第三章】《哈夫曼编码构造及代码》
37【第四章】《图的定义》
38【第四章】《图的基本概念和术语》
39【第四章】《图的存储结构》
40【第四章】《图的遍历之深度优先遍历》
41【第四章】《广度优先遍历BFS》
42【第四章】《图的遍历总代码》
43【第四章】《最小生成树概念》
44【第四章】《最小生成树的应用举例》
45【第四章】《prim算法（普里姆算法）详解》
46【第四章】《prim算法（普里姆算法）详解2》
47【第四章】《prim算法（普里姆算法）详解3》
48【第四章】《prim算法（普里姆算法）讲解汇总》
49【第四章】《prim算法（普里姆算法）代码讲解》
50【第四章】《prim算法（普里姆算法）总代码》
51【第四章】《克鲁斯卡尔算法思路介绍》
52【第四章】《克鲁斯卡尔算法步骤思路1》
53【第四章】《克鲁斯卡尔算法步骤思路2》
54【第四章】《克鲁斯卡尔算法应用场景-公交站问题》
55【第四章】《克鲁斯卡尔算法判断回路问题》
56【第四章】《克鲁斯卡尔算法步骤回顾》
57【第四章】《克鲁斯卡尔算法代码初始化详解》
58【第四章】《克鲁斯卡尔算法总代码详解》
59【第四章】《了解最短路径》
60【第四章】《迪杰斯特拉算法了解》
61【第四章】《Dijkstra 迪杰斯特拉算法图解》
62【第四章】《Dijkstra 迪杰斯特拉算法总代码》
63【第四章】《弗洛伊德(floyd)算法简介》
64【第四章】《弗洛伊德算法详解》
65【第四章】《弗洛伊德代码详解》
66【第四章】《拓扑排序之AOV网》
67【第四章】《拓扑排序介绍及其方法》
68【第四章】《拓扑排序代码详解》
69【第四章】《什么是关键路径》
70【第四章】《什么是关键路径二》
71【第四章】《关键活动与最早路径实现思想》
72【第四章】《关键活动与最早路径实现思想写法二》
73【第四章】《关键路径总代码讲解写法一》
74【第四章】《关键路径总代码讲解写法二》
75【第五章】《顺序查找》
76【第五章】《顺序查找-带哨兵》


http://www.ppmy.cn/ops/105104.html

相关文章

如何禁止电脑访问网站

如何禁止电脑访问网站

一、修改Hosts文件 找到Hosts文件&#xff1a;在Windows系统中&#xff0c;Hosts文件通常位于C:\Windows\System32\drivers\etc\目录下。 编辑Hosts文件&#xff1a;以管理员身份打开记事本或任意文本编辑器&#xff0c;然后找到并打开Hosts文件。 添加禁止访问的域名&#…
阅读更多...
【RabbitMQ】核心概念

【RabbitMQ】核心概念

界⾯上的导航栏共分6部分, 这6部分分别是什么意思呢, 我们先看看RabbitMQ的工作流程 1. Producer和Consumer Producer:生产者,是RabbitMQ Server的客户端,向RabbitMQ发送消息 Consumer: 消费者,也是RabbitMQ Server的客户端,从RabbitMQ接收消息 Broker:其实就是RabbitMQSer…
阅读更多...
HTB-Runner靶机笔记

HTB-Runner靶机笔记

HTB-Runner靶机笔记 概述 Runner是HTB上一个中等难度的Linux靶机&#xff0c;它包含以下teamcity漏洞(CVE-2023-42793)该漏洞允许用户绕过身份验证并提取API令牌。以及docker容器逃逸CVE-2024-21626&#xff0c;进行提权操作 Runner靶机地址&#xff1a;https://app.hackthe…
阅读更多...
Java SpringBoot构建在线培训平台，集成Vue实现课程发布，打造互动学习体验

Java SpringBoot构建在线培训平台，集成Vue实现课程发布，打造互动学习体验

✍✍计算机毕业编程指导师** ⭐⭐个人介绍&#xff1a;自己非常喜欢研究技术问题&#xff01;专业做Java、Python、微信小程序、安卓、大数据、爬虫、Golang、大屏等实战项目。 ⛽⛽实战项目&#xff1a;有源码或者技术上的问题欢迎在评论区一起讨论交流&#xff01; ⚡⚡ Java…
阅读更多...
ESD防静电监控系统助力电子制造行业转型升级

ESD防静电监控系统助力电子制造行业转型升级

在电子制造行业中&#xff0c;静电危害不容小觑。ESD 防静电监控系统的出现&#xff0c;为行业转型升级带来强大助力。电子元件对静电极为敏感&#xff0c;微小的静电放电都可能损坏元件&#xff0c;影响产品质量。ESD 防静电监控系统能够实时监测生产环境中的静电状况&#xf…
阅读更多...
后台框架-统一数据格式

后台框架-统一数据格式

现在BS架构的应用一般都采用前后端分离的架构&#xff0c;前端技术框架可采用VUE等&#xff0c;后端框架目前成熟且使用广泛的就是基于SpringBoot开发的后端微服务框架。 数据格式 这里主要介绍一下如何实现返回统一的数据格式&#xff0c;比如返回的样例数据如下图所示&…
阅读更多...
【LeetCode】温度转换 最小偶倍数 二叉树判断根节点

【LeetCode】温度转换 最小偶倍数 二叉树判断根节点

温度转换题目&#xff1a; 给你一个四舍五入到两位小数的非负浮点数 celsius 来表示温度&#xff0c;以 摄氏度&#xff08;Celsius&#xff09;为单位。 你需要将摄氏度转换为 开氏度&#xff08;Kelvin&#xff09;和 华氏度&#xff08;Fahrenheit&#xff09;&#xff0c…
阅读更多...
服务器数据恢复—磁盘坏扇区导致raid6阵列崩溃的数据恢复案例

服务器数据恢复—磁盘坏扇区导致raid6阵列崩溃的数据恢复案例

服务器存储数据恢复环境&#xff1a; 一台存储中有一组由12块SAS硬盘组建的raid6磁盘阵列&#xff0c;划分了1个卷&#xff0c;由数台Vmware ESXI主机共享存储。卷中存放了大量的Windows系统虚拟机。这些虚拟机系统盘大小一致&#xff0c;数据盘大小不确定&#xff0c;数据盘都…
阅读更多...
最新文章

Copyright @ 2022~2023