从0开始学习数据结构 C语言实现 1.前篇及二分查找算法

一、前篇

1、什么是数据结构?

数据结构是带有结构特性的数据元素的集合,它研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系

 2、时间复杂度与空间复杂度

大O符号是用于描述函数渐进行为的数学符号

常用函数的增长表

阶乘O(n!) > 指数阶(2^n) > 立方阶O(n^3) > 平方阶O(n^2) > 线性对数阶O(nlog2n) > 线性阶O(n) > 对数阶O(log2n) > 常数阶O(1)

从立方阶开始,时间复杂度较大

二、二分查找

在有序数组中查找一个值,如果找到了则返回下标,如果没找到则返回-1

方法一:遍历数组进行查找

时间复杂度:O(n)

//1.遍历算法在数组中查找一个元素
//方法体
int search(int* arr, int length, int target) {for (int i = 0; i < length; i++) {if (arr[i] == target) {return i;}}
}

方法二:减小循环次数进行遍历查找

时间复杂度小于O(n)

因为题目里声明是有序数组,所以当数组中的值比查找的值大时,可以直接break跳出循环,减少循环次数

//2.减小循环次数进行遍历查找
//方法体
int search2(int* arr, int length, int target) {for (int i = 0; i < length; i++) {if (arr[i] == target) {return i;}if (arr[i] > target) {break;}}return -1;
}

方法三;二分查找

二分思想就是将一个 有序数组 不断进行平分,直到找到为止,不断平分除以二,降低时间复杂度

时间复杂度:O(og2n)

//3.二分查找
//方法体
int binarySearch(int* arr, int target, int left, int right) {if (left > right) {return -1;}int mid = (left + right) / 2;if (arr[mid] == target) {return mid;}if (arr[mid] > target) {mid = binarySearch(arr, target, left, mid - 1);return mid;}else {mid = binarySearch(arr, target, mid + 1, right);return mid;}
}int search3(int* arr, int length, int target) {return binarySearch(arr, target, 0, length - 1);
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/197992.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

LeetCode - 26. 删除有序数组中的重复项 (C语言,快慢指针,配图)

力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台 思路一&#xff1a;快慢指针 在数组中&#xff0c;快慢指针就是两个整数下标&#xff0c;定义 fast 和 slow 这里我们从下标1开始&#xff08;下标0的数据就1个&#xff0c;没有重复项&#xff09;&…

Flutter最新稳定版3.16 新特性介绍

Flutter 3.16 默认采用 Material 3 主题&#xff0c;Android 平台预览 Impeller&#xff0c;DevTools 扩展等等 Flutter在每个季度通常都会有个稳定版本的发布。在2023 Q4的更新中为大家带来的是Flutter 3.16。这个版本将 Material 3 设为新的默认主题&#xff0c;并为 Android…

人生阶段总结

--回顾一下我迷茫、努力、不开心又失败的阶段人生自我介绍一下&#xff0c;我是一个智力平平&#xff0c;记忆力差&#xff0c;适合自学的长睡眠者。 大专之前 国内的应试教育基本上不适合我&#xff0c;厌恶补课厌恶机械式听课刷题&#xff0c;所有的优势学科都是自学&#xf…

Unity中Shader法线贴图(上)

文章目录 前言一、法线纹理的作用二、为什么法线贴图长这样&#xff1f;&#xff08;蓝色&#xff09;三、法线贴图能使纹理采样时&#xff0c;进行偏移采样四、在Shader中使用法线贴图1、在属性面板定义一个变量来接收法线贴图2、在使用前声明 _NormalTex3、在片元着色器中&am…

【Go入门】Web工作方式

【Go入门】 Web工作方式 我们平时浏览网页的时候,会打开浏览器&#xff0c;输入网址后按下回车键&#xff0c;然后就会显示出你想要浏览的内容。在这个看似简单的用户行为背后&#xff0c;到底隐藏了些什么呢&#xff1f; 对于普通的上网过程&#xff0c;系统其实是这样做的&…

内容运营工具:标签体系

一.分类和标签的区别 ■标签是扁平的&#xff0c;分类是层级的。 ■标签是精确的&#xff0c;分类是粗糙的。 ■标签是多维的&#xff0c;分类是一维的。 二.标签的本质&#xff1a;元数据 事实上&#xff0c;在数据领域&#xff0c;有一个鼎鼎大名的词汇与标签极其雷同&…

Python爬虫的七个常用技巧总结,这些你一定得知道!

文章目录 前言1、基本抓取网页2、使用代理IP3、Cookies处理4、伪装成浏览器5、验证码的处理6、gzip压缩7、多线程并发抓取关于Python技术储备一、Python所有方向的学习路线二、Python基础学习视频三、精品Python学习书籍四、Python工具包项目源码合集①Python工具包②Python实战…

锐捷EG易网关login.php以及其后台cli.php/branch_passw.php RCE漏洞复现 [附POC]

文章目录 锐捷EG易网关login.php以及其后台cli.php/branch_passw.php远程代码执行漏洞复现 [附POC]0x01 前言0x02 漏洞描述0x03 影响版本0x04 漏洞环境0x05 漏洞复现1.访问漏洞环境2.构造POC3.复现 锐捷EG易网关login.php以及其后台cli.php/branch_passw.php远程代码执行漏洞复…

Mysql -常见函数

目录 字符串函数 数值函数 日期函数 流程函数 字符串函数 -- 拼接 SELECT CONCAT(Hello, World); -- 小写 SELECT LOWER(Hello); -- 大写 SELECT UPPER(Hello); -- 左填充 SELECT LPAD(01, 5, -); -- 右填充 SELECT RPAD(01, 5, -); -- 去除空格 SELECT TRIM( Hello World )…

批量替换WordPress文章内图片链接

在WordPress使用过程中&#xff0c;如果中途更换了域名&#xff0c;原先文章内的图片使用的是原来的域名&#xff0c;就会造成文章页里面的图片链接无法显示。如果从后台文章挨个修改就比较麻烦。可以通过数据库进行批量替换即可。 使用 PHPMyadmin 打开 数据库&#xff0c;登…

【C++】一文全解C++中的异常:标准库异常体系&自定义异常体系(含代码演示)

前言 大家好吖&#xff0c;欢迎来到 YY 滴C系列 &#xff0c;热烈欢迎&#xff01; 本章主要内容面向接触过C的老铁 主要内容含&#xff1a; 欢迎订阅 YY滴C专栏&#xff01;更多干货持续更新&#xff01;以下是传送门&#xff01; 目录 一.C语言传统的处理错误的方式二.C异常…

修完这个 Bug 后,MySQL 性能提升了 300%

最近 MySQL 官方在 8.0.35 上修复了一个 bug&#xff1a; 这个 bug 是由 Mark Callaghan 发现的。Mark 早年在 Google MySQL 团队&#xff0c;后来去了 Meta MySQL&#xff0c;也主导了 RocksDB 的开发。 Mark 在 #109595 的 bug report 给出了非常详细的复现步骤 在官方修复后…

【网络通信】探索UDP与TCP协议、IP地址和端口号的奥妙

&#x1f33a;个人主页&#xff1a;Dawn黎明开始 &#x1f380;系列专栏&#xff1a;网络奇幻之旅 ⭐每日一句&#xff1a;往前走&#xff0c;朝着光 &#x1f4e2;欢迎大家&#xff1a;关注&#x1f50d;点赞&#x1f44d;评论&#x1f4dd;收藏⭐️ 文章目录 &#x1f4cb;前…

【Web】Ctfshow SSTI刷题记录1

目录 ①web361 362-无过滤 ②web363-过滤单双引号 ③web364-过滤单双引号和args ④web365-过滤中括号[]、单双引号、args ⑤web366-过滤单双引号、args、中括号[]、下划线 ⑦web367-过滤单双引号、args、中括号[]、下划线、os ⑧web368-过滤单双引号、args、中括号[]、下…

如何在 Nginx Proxy Manager(NPM)上部署静态网站

前言 众所周知&#xff0c;我们在之前介绍过 Nginx Proxy Manager&#xff08;以下简称 NPM) 这个反向代理的神器&#xff0c;对于一些 Docker 搭建的 Web 项目&#xff0c;NPM 能够很轻松地给他们做反向代理。 然而对于一些静态网站&#xff0c;小伙伴们可能不知道怎么用 NP…

Ubuntu 安装VMware Tools选项显示灰色,如何安装VMware Tools

切换apt源为阿里云&#xff1a; https://qq742971636.blog.csdn.net/article/details/134291339 只要你的网络没问题&#xff0c;你直接执行这几个命令&#xff0c;重启ubuntu虚拟机即可、 sudo dpkg --configure -a sudo apt-get autoremove open-vm-tools sudo apt-get ins…

LangChain 2模块化prompt template并用streamlit生成网站 实现给动物取名字

上一节实现了 LangChain 实现给动物取名字&#xff0c; 实际上每次给不同的动物取名字&#xff0c;还得修改源代码&#xff0c;这周就用模块化template来实现。 1. 添加promptTemplate from langchain.llms import OpenAI # 导入Langchain库中的OpenAI模块 from langchain.p…

Autox.js和Auto.js4.1.1手机编辑器不好用我自己写了一个编辑器

功能有 撤销 重做 格式化 跳转关键词 下面展示一些 内联代码片。 "ui"; ui.layout( <drawer id"drawer"><vertical><appbar><toolbar id"toolbar"title""h"20"/></appbar><horizontal b…

深度学习——(生成模型)DDPM

前置数学知识 1、先验概率和后验概率 先验概率&#xff1a;根据以往经验和分析得到的概率,它往往作为“由因求果”问题中的“因”出现&#xff0c;如 q ( x t ∣ x t − 1 ) q(x_t|x_{t-1}) q(xt​∣xt−1​) 后验概率&#xff1a;指在得到“结果”的信息后重新修正的概率,是…

MIKE水动力笔记19_统计平均潮差

本文目录 前言Step 1 ArcGIS中创建渔网点Step 2 将dfsu数据提取到渔网点Step 3 Python统计平均潮差 前言 日平均潮差&#xff08;average daily tidal range&#xff09;&#xff1a;日高潮潮高合计之和除以实有高潮个数为日平均高潮潮高&#xff0c;日低潮潮高合计之和除以实…