当前位置: 首页 > news >正文

C:每日一题:二分查找

1、知识介绍:

1.1 概念:

二分查找是一种在有序数组中查找某一特定元素的搜索算法

1.2 基本思想:

每次将待查找的范围缩小一半,通过比较中间元素与目标元素的大小,来决定是在左半部分还是右半部分继续查找。

举个生活中的小例子:

比如说你朋友和你说她买了一件衣服价格不超过300元,然后让你猜一猜具体的价格,你肯定不会像 1 2 3……这样一个一个猜,而是先猜中间值150,如果实际价格比150大,则0~150之间的数字就不需要再猜,此时范围便缩小到150~300;这时候再猜225,如果实际价格小于225元,则225~300之间的数字就不需要再猜了,经过这样几次的猜测后,范围会逐渐缩小,大大提高了猜中数字的效率,这种思想就是二分查找。

1.3 二分查找的优缺点:

优点:二分查找的效率很高,在查找有序数组中的数字时,比遍历数组的效率高很多;

不足:二分查找的使用条件很苛刻,只有在有序数组中才能使用二分查找。

2、题目

写一个二分查找函数

功能:在一个升序数组中查找指定的数值,找到了就返回下标,找不到就返回-1.

int arr[ 10] = {11,23,23,56,77,88,98,111,121,131}

3、思路:

关于查找数组中的元素,我们一般是通过下标来锁定元素

3、 分析main函数

int main()
{int arr[] = {11,23,23,56,77,88,98,111,121,131};int k = 0;scanf("%d", &k);//输入想要找的值int sz = sizeof(arr) / sizeof(arr[0]);//获取元素个数int left = 0;int right = sz - 1;int result = bin_search(arr, left, right, k);if (result != -1) {printf("找到了,下标为: %d\n", result);}else {printf("未找到\n");}return 0;
}

3.1  代码解释int left = 0; int right = sz - 1;

 3.2 代码解释 int result = bin_search(arr, left, right, k);

 bin_search是一个自定义函数,用来实现二分查找的过程

int result = bin_search(arr, left, right, k);是调用了一个名为 bin_search 的函数,并将返回值存储在变量  result 中。

  • arr 是要进行查找操作的数组。
  •  left 和 right 分别是数组的起始下标和结束下标,确定了当前要查找的范围。
  • k 是要在数组中查找的目标值。

4、分析函数bin_search

int bin_search(int arr[], int left, int right, int k)
{int mid = (left + right) / 2;while (left <= right){int mid = (left + right) / 2;if (arr[mid] < k){left = mid + 1;}else if (arr[mid] > k){right = mid - 1;}else{return mid;}}return -1;
}

4.1 二分查找的运算方式:

5、完整代码

#include <stdio.h>
int bin_search(int arr[], int left, int right, int k)
{int mid = (left + right) / 2;while (left <= right){int mid = (left + right) / 2;if (arr[mid] < k){left = mid + 1;}else if (arr[mid] > k){right = mid - 1;}else{return mid;}}return -1;
}int main()
{int arr[] = {11,23,23,56,77,88,98,111,121,131};int k = 0;scanf("%d", &k);int sz = sizeof(arr) / sizeof(arr[0]);int left = 0;int right = sz - 1;int result = bin_search(arr, left, right, k);if (result != -1) {printf("找到了,下标为: %d\n", result);}else {printf("未找到\n");}return 0;
}

  函数bin_search  会在给定的数组范围 left 到  right 内查找目标值 k ,并返回找到目标值时的下标或者 -1 表示未找到。然后这个返回值就被赋值给了 result  ,后续的代码会根据 result  的值来判断是否找到了目标值。

6、不使用函数的二分查找

#include <stdio.h>
int main()
{int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };int k = 7;scanf("%d", &k);int sz = sizeof(arr) / sizeof(arr[0]);int left = 0;int right = sz - 1;int flag = 0;while(left <= right){int mid = (left + right) / 2;if (arr[mid] < k){left = mid + 1;}else if (arr[mid] > k){right = mid - 1;}else{printf("找到了,下标位%d\n", mid);flag = 1;break;}}if (flag == 0)printf("没找到");return 0;
}

如果觉得还不错的话,就给小编一个三连吧!!!

相关文章:

C:每日一题:二分查找

1、知识介绍&#xff1a; 1.1 概念&#xff1a; 二分查找是一种在有序数组中查找某一特定元素的搜索算法 1.2 基本思想&#xff1a; 每次将待查找的范围缩小一半&#xff0c;通过比较中间元素与目标元素的大小&#xff0c;来决定是在左半部分还是右半部分继续查找。 举个生…...

python Django中使用ORM进行分组统计并降序排列

python Django中使用ORM进行分组统计并降序排列 # 使用supplier和Count进行分组统计,其中supplier为MyModel的一个字段 supplier_counts MyModel.objects.values(supplier).annotate(countCount(supplier)).order_by(-count) # 输出统计结果 for supplier_count in supplier_…...

QT C++ 编写modbus 总结

[开源库的使用]libModbus编译及使用_libmodbus库-CSDN博客 libmodbus的下载与编译_modbus库文件下载-CSDN博客 【QT5】解决 QT 界面中文显示乱码问题_qt5输出中文乱码解决方法-CSDN博客 Qt&#xff1a;解决qt修改完ui文件起不到作用_qt ui文件修改后不生效-CSDN博客...

基于SpringBoot的网络海鲜市场系统的设计与实现

TOC springboot219基于SpringBoot的网络海鲜市场系统的设计与实现 绪论 1.1 选题背景 当人们发现随着生产规模的不断扩大&#xff0c;人为计算方面才是一个巨大的短板&#xff0c;所以发明了各种计算设备&#xff0c;从结绳记事&#xff0c;到算筹&#xff0c;以及算盘&…...

c#相关基础知识

c#参数4种种别 值参&#xff1a;像Java的正常数据的传输 ref&#xff1a;对参数的指向是参数本身的地址&#xff0c;而不是数据的副本&#xff0c;所以可以对数据进行直接操作 out: 绑定控件&#xff0c;控件传输值赋值给类中的内部类 待定...

注意力机制 — 它是什么以及它是如何工作的

一、说明 注意力机制是深度学习领域的一个突破。它们帮助模型专注于数据的重要部分&#xff0c;并提高语言处理和计算机视觉等任务的理解和性能。这篇文章将深入探讨深度学习中注意力的基础知识&#xff0c;并展示其背后的主要思想。 二、注意力机制回顾 在我们谈论注意力之前&…...

学习嵌入式第二十六天

进程线程 1.进程的概念 2.进程 和 程序 硬盘中程序 &#xff0c;加载到内存中&#xff0c;运行起来&#xff0c;就是进程 创建线程 pthread_create posix thread create 线程执行 ---体现在线程执行函数 (回调函数) 线程退出 ---pthread_exit() …...

speech语音audio音频

在信号处理和语言技术领域&#xff0c;speech 和 audio 是两个相关但不同的概念。它们有各自的定义和应用场景。以下是对这两个术语的详细解释&#xff1a; 1. Speech&#xff08;语音&#xff09; Speech 主要指的是人类说话时产生的声音。它是人类语言交流的一种主要形式&a…...

最常用的正则表达式规则和语法

正则表达式(Regular Expression,简称 regex)是一种用于匹配字符串的强大工具。它使用特定的语法规则来定义字符串模式,可以用来搜索、替换、验证字符串等。以下是一些常用的正则表达式规则和语法: 1. 基本字符匹配 . :匹配任意单个字符(除了换行符)。 示例:a.c 可以匹…...

Datawhale X 魔搭 AI夏令营第四期-魔搭生图task1学习笔记

根据教程提供的链接&#xff0c;进入相应文章了解魔搭生图的主要工作是通过对大量图片的训练&#xff0c;生成自己的模型&#xff0c;然后使用不同的正向、反向提示词使模型输出对应的图片 1.官方跑baseline教程链接:Task 1 从零入门AI生图原理&实践 2.简单列举一下赛事的…...

WPF中XAML相对路径表示方法

在WPF XAML中&#xff0c;相对路径是一种非常实用的方式来引用资源文件&#xff0c;如图像、样式表和其他XAML文件。相对路径可以帮助您构建更加灵活和可移植的应用程序&#xff0c;因为它允许资源文件的位置相对于XAML文件的位置进行定位。 相对路径的表示方法 在XAML中&…...

操作系统内存管理技术详解

操作系统内存管理技术详解&#xff1a;第一部分 引言 操作系统作为计算机系统的核心组件&#xff0c;负责管理硬件资源、提供用户接口和运行应用程序。在操作系统的众多功能中&#xff0c;内存管理无疑是最为关键的技术之一。本文将深入探讨操作系统内存管理的背后技术&…...

python之numpy(2 创建矩阵)

numpy创建矩阵 前面提到&#xff0c;numpy主要是针对数组和矩阵的操作。下面我们分别创建数组和矩阵。 import numpy as np x0np.array([1,2,3,4]) x1np.array([[1,2,3,4],[1,2,3,4]]) print(x0,x1,sep\n) 在numpy中&#xff0c;使用array创建数组和矩阵。其中&#xff0c;创…...

git stage 和 git unstage

无意间遇到 git stage 和 git unstage&#xff0c;感觉有点陌生&#xff0c;简单了解一下这两个概念。 在 Git 中&#xff0c;stage 和 unstage 是与暂存区操作相关的术语&#xff0c;它们用于管理文件的状态&#xff0c;决定哪些更改会在下次的提交中。 1. git stage git s…...

C#使用反射和特性的优缺点

使用反射&#xff08;Reflection&#xff09;和特性&#xff08;Attributes&#xff09;在C#中有其特定的应用场景&#xff0c;同时也带来了一些优缺点&#xff1a; 反射的优点&#xff1a; 动态性&#xff1a;反射允许程序在运行时查询和操作对象的类型信息&#xff0c;提供…...

C语言:字符串函数strcat

该函数用于字符串拼接。 使用方法如下&#xff1a; #include<stdio.h> #include<string.h>int main() {char str[20] "abcd";char str1[] "1234";//strcat(str,str1);//不安全&#xff0c;所以用strcat_sstrcat_s(str, 20, str1);printf(&…...

haproxy总结与实验

一、负载均衡 1.1 简述负载均衡 在高并发的业务场景下&#xff0c;解决单个节点压力过大&#xff0c;导致Web服务响应过慢&#xff0c;特别是严重的情况下导致服务瘫痪&#xff0c;无法正常提供服务的问题&#xff0c;而负载均衡的目的就是为了维护系统稳定可靠。负载均衡&…...

VS实用调试技巧(程序员的必备技能)

调试的重要性 在我们写代码的时候&#xff0c;如果程序出现了bug&#xff0c;那么下一步就是找到bug并修复bug!而这个找问题的过程就被称为调试&#xff08;英文叫debug&#xff0c;消灭bug的意思&#xff09;。 调试能观察到程序内部执行的细节&#xff0c;可以增加程序员对…...

怎样卸载python

python卸载干净的具体操作步骤如下&#xff1a; 1、首先打开电脑左下角开始菜单&#xff0c;点击“运行”选项&#xff0c;输入“cmd”。 2、输入“python --version”&#xff0c;得到一个程序的版本&#xff0c;按回车键。 3、点击下图程序。 4、然后在该页面中点击“uninst…...

SQL注入靶场攻击——sqli-labs

一、概述 SQL注入&#xff08;SQL Injection&#xff09;是发生在web程序中数据库层的安全漏洞&#xff0c;是比较常用的网络攻击方式之一&#xff0c;它不是利用操作系统的BUG来实现攻击&#xff0c;而是针对程序员编写时的疏忽&#xff0c;通过SQL语句&#xff0c;实现无账号…...

挑战杯推荐项目

“人工智能”创意赛 - 智能艺术创作助手&#xff1a;借助大模型技术&#xff0c;开发能根据用户输入的主题、风格等要求&#xff0c;生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用&#xff0c;帮助艺术家和创意爱好者激发创意、提高创作效率。 ​ - 个性化梦境…...

SkyWalking 10.2.0 SWCK 配置过程

SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外&#xff0c;K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案&#xff0c;全安装在K8S群集中。 具体可参…...

遍历 Map 类型集合的方法汇总

1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

NFT模式:数字资产确权与链游经济系统构建

NFT模式&#xff1a;数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新&#xff1a;构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议&#xff1a;基于LayerZero协议实现以太坊、Solana等公链资产互通&#xff0c;通过零知…...

uniapp中使用aixos 报错

问题&#xff1a; 在uniapp中使用aixos&#xff0c;运行后报如下错误&#xff1a; AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...

是否存在路径(FIFOBB算法)

题目描述 一个具有 n 个顶点e条边的无向图&#xff0c;该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序&#xff0c;确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数&#xff0c;分别表示n 和 e 的值&#xff08;1…...

虚拟电厂发展三大趋势:市场化、技术主导、车网互联

市场化&#xff1a;从政策驱动到多元盈利 政策全面赋能 2025年4月&#xff0c;国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》&#xff0c;首次明确虚拟电厂为“独立市场主体”&#xff0c;提出硬性目标&#xff1a;2027年全国调节能力≥2000万千瓦&#xff0…...

go 里面的指针

指针 在 Go 中&#xff0c;指针&#xff08;pointer&#xff09;是一个变量的内存地址&#xff0c;就像 C 语言那样&#xff1a; a : 10 p : &a // p 是一个指向 a 的指针 fmt.Println(*p) // 输出 10&#xff0c;通过指针解引用• &a 表示获取变量 a 的地址 p 表示…...

【堆垛策略】设计方法

堆垛策略的设计是积木堆叠系统的核心&#xff0c;直接影响堆叠的稳定性、效率和容错能力。以下是分层次的堆垛策略设计方法&#xff0c;涵盖基础规则、优化算法和容错机制&#xff1a; 1. 基础堆垛规则 (1) 物理稳定性优先 重心原则&#xff1a; 大尺寸/重量积木在下&#xf…...

云安全与网络安全:核心区别与协同作用解析

在数字化转型的浪潮中&#xff0c;云安全与网络安全作为信息安全的两大支柱&#xff0c;常被混淆但本质不同。本文将从概念、责任分工、技术手段、威胁类型等维度深入解析两者的差异&#xff0c;并探讨它们的协同作用。 一、核心区别 定义与范围 网络安全&#xff1a;聚焦于保…...