算法学习之二分查找

🎃个人主页🎃:勇敢的小牛儿

🧨推荐专栏🧨:C语言知识点

✨座右铭✨:敢于尝试才有机会

⚠️今日鸡汤⚠️:Is the true wisdom fortitude ambition. -- Napoleon

                           真正的才智是刚毅的志向-----拿破仑

目录

一,二分查找法介绍:

二,例题: 

 2.1题目介绍:

2.2题目接口:

 三,题目解答:

1.确定循环的范围:

2.选择区间:

3.选择左闭右开的区间:[left,right)

结语:


一,二分查找法介绍:

二分法其实就是在一个数组中找一个target然后返回这个元素的数组下标。但是这个数组一定要是有序的。

二,例题: 

🌰例题🌰:704. 二分查找 

 2.1题目介绍:

给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target  ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。

2.2题目接口:

int search(int* nums, int numsSize, int target){

}

 三,题目解答:

1.确定循环的范围:

 面对这三剑客,我们应该怎么选呢?

2.选择区间:

2.1选择左闭右闭区间:[left,right]:

其实这里的左闭右闭的意思就是left与right代表的两个下标都在数组下标的范围之内,所以这里的left = 0;right = numsSize - 1。

所以我们在定义left与right时代码就这样写:

int search(int* nums, int numsSize, int target) {
	int left = 0;
	int right = numsSize - 1;

}

现在我们已经定义了两个端点值了,既然是二分查找法,那必定有mid。我们的mid 该如何写呢?

这里有两种写法:

mid = (right + left)/2;

mid =  left +(right - left)/2;

为了防止溢出现象的出现,我们便把mid写成:mid = left + (right - left)/2;

int search(int* nums, int numsSize, int target) {
	int left = 0;
	int right = numsSize - 1;
	int mid = left + (right - left) / 2;

}

 2.2循环的终止条件:left<right?left<=right?

    因为在这里我选择的是一个左闭右闭的区间,所以我们的while的判断条件内left==right是不是合法的呢?

    我们的答案是,是的。比如:[1,1],这个1在这个左闭右闭区间内是一个合法的值吧。既然合法那我们就得去判断。所以这里的终止条件是:left<=right。

int search(int* nums, int numsSize, int target) {
	int left = 0;
	int right = numsSize - 1;
	int mid = left + (right - left) / 2;
	while (left <= right) {

	}

}

 2.3搜索范围的调整:

2.3.1:nums[mid]>target时right=mid?right=mid-1?

 当代码是这种情况时,我们要找到target在数组中的下标的。因为我们已经判断过了target<nums[mid]。所以nums[mid]就一定不在我们要找的范围内,所以我们在缩小寻找的范围时就要把nums[mid]排除在外,所以right=mid-1

 2.3.2::nums[mid]<target时left=mid?left=mid+1?

 

当代码是这种情况时,我们的left=mid,还是mid - 1呢?其实在我们判断完nums[mid]<target时,mid下标所指向的值就要被排除在搜索范围之内,所以left=mid+1。

代码:

int search(int* nums, int numsSize, int target) {
	int left = 0;
	int right = numsSize - 1;
	int mid = left + (right - left) / 2;
	while (left <= right) {
		mid = left + (right - left) / 2;
		if (nums[mid] > target) {
			right = mid - 1;
		}
		else if (nums[mid] < target) {
			left = mid + 1;}
		
	}
	
}

2.4全部代码:

int search(int* nums, int numsSize, int target) {
	int left = 0;
	int right = numsSize - 1;
	int mid = left + (right - left) / 2;
	while (left <= right) {
		mid = left + (right - left) / 2;
		if (nums[mid] > target) {
			right = mid - 1;
		}
		else if (nums[mid] < target) {
			left = mid + 1;
		}
		else {
			return mid;
		}
	}
	return -1;
}

3.选择左闭右开的区间:[left,right)

在这里,左闭右开的意思就是left代表的值在数组下标的范围之内,right代表的的下标不在数组下标所表示的范围之内。我们可以定义:left=0,right=numsSize

int search(int* nums, int numsSize, int target) {
	int left = 0;
	int right = numsSize ;
    mid = left + (right - left)/2;


}

3.1while循环的终止条件:

因为我们选择的是左开右闭的区间,所以循环的终止条件应该是left<right而没有left=right这个条件。为什么?比如你的区间是[1,2),当你的值为2时,你的数值其实已经不再区间范围之内了,所以我们就不需要再判断了。

int search(int* nums, int numsSize, int target) {
	int left = 0;
	int right = numsSize ;
	int mid = left + (right - left) / 2;
	while (left <right) {

	}

}

3.2搜索范围的调整:

3.2.1 当nums[mid]>target时right=mid?right=mid-1?

 当我们的nums[mid]>target时,我们应该怎样调整right的值呢?这里因该把right调整为mid。因为你是一个开区间,right的值原本就是在数组下标范围之外的,所以mid=left+(right-left)/2其实是一个没有被搜索过的下标。所以,在这里就要更新为right = mid.

int search(int* nums, int numsSize, int target) {
	int left = 0;
	int right = numsSize ;
	int mid = left + (right - left) / 2;
	while (left <right) {
		mid = left + (right - left) / 2;
		if (target < nums[mid]) {
			right = mid;
		}

	}

}

 3.2.2当nums[mid]<target时,left=mid?left=mid-1?

其实这里的情况和左闭右闭时的处理是一样的,因为都是左闭区间。所以,left=mid+1

int search(int* nums, int numsSize, int target) {
	int left = 0;
	int right = numsSize ;
	int mid = left + (right - left) / 2;
	while (left <right) {
		mid = left + (right - left) / 2;
		if (target < nums[mid]) {
			right = mid;
		}
		else if (target > nums[mid]) {
			left = mid + 1;
		}
	}

}

3.3全部代码:

int search(int* nums, int numsSize, int target) {
	int left = 0;
	int right = numsSize ;
	int mid = left + (right - left) / 2;
	while (left < right) {
		mid = left + (right - left) / 2;
		if (nums[mid] > target) {
			right = mid ;
		}
		else if (nums[mid] < target) {
			left = mid + 1;
		}
		else {
			return mid;
		}
	}
	return -1;
}

结语:

剩下的一个就交给各位看官来解决吧。小牛儿今天的分享就到这里了,谢谢您的阅读。如果可以的话,给小牛儿来个三连呗。 

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【云原生·Docker】常用命令

目录 &#x1f341;1、管理命令 &#x1f341;2、帮助命令 &#x1f341;3、镜像命令 &#x1f341;4、容器命令 &#x1f342;4.1.查看容器 &#x1f342;4.2.创建容器 &#x1f342;4.3.删除容器 &#x1f342;4.4.拷贝文件 &#x1f342;4.5.查看容器IP &#x1f341;5、部署…

LSTM从入门到精通(形象的图解,详细的代码和注释,完美的数学推导过程)

先附上这篇文章的一个思维导图什么是RNN按照八股文来说&#xff1a;RNN实际上就是一个带有记忆的时间序列的预测模型RNN的细胞结构图如下&#xff1a;softmax激活函数只是我举的一个例子&#xff0c;实际上得到y<t>也可以通过其他的激活函数得到其中a<t-1>代表t-1时…

C语言/动态通讯录

本文使用了malloc、realloc、calloc等和内存开辟有关的函数。 文章目录 前言 二、头文件 三、主界面 四、通讯录功能函数 1.全代码 2.增加联系人 3.删除联系人 4.查找联系人 5.修改联系人 6.展示联系人 7.清空联系人 8.退出通讯录 总结 前言 为了使用通讯录时&#xff0c;可以…

Opencv项目实战:22 物体颜色识别并框选

目录 0、项目介绍 1、效果展示 2、项目搭建 3、项目代码展示与部分讲解 Color_trackbar.py bgr_detector.py test.py 4、项目资源 5、项目总结 0、项目介绍 本次项目要完成的是对物体颜色的识别并框选&#xff0c;有如下功能&#xff1a; &#xff08;1&#xff09;…

线程池的使用:如何写出高效的多线程程序?

目录1.线程池的使用2.编写高效的多线程程序Java提供了Executor框架来支持线程池的实现&#xff0c;通过Executor框架&#xff0c;可以快速地创建和管理线程池&#xff0c;从而更加方便地编写多线程程序。 1.线程池的使用 在使用线程池时&#xff0c;需要注意以下几点&#xff…

GDAL python教程基础篇(7)OGR空间计算

1.空间计算 地理数据处理&#xff08;geoprocessing&#xff09;计算函数&#xff1a; 多边形&#xff08;Polygon&#xff09;&#xff1a; 1、交&#xff1a;poly3.Intersection(poly2) 2、并&#xff1a;poly3.Union(poly2) 3、差&#xff1a;poly3.Difference(poly2) 4、补…

python打包成apk界面设计,python打包成安装文件

大家好&#xff0c;给大家分享一下如何将python程序打包成apk文件&#xff0c;很多人还不知道这一点。下面详细解释一下。现在让我们来看看&#xff01; 1、如何用python制作十分秒加减的apk 如何用python制作十分秒加减的apk&#xff1f;用法:. apk包放入apk文件目录,然后输入…

Linux基础命令大全(下)

♥️作者&#xff1a;小刘在C站 ♥️个人主页&#xff1a;小刘主页 ♥️每天分享云计算网络运维课堂笔记&#xff0c;努力不一定有收获&#xff0c;但一定会有收获加油&#xff01;一起努力&#xff0c;共赴美好人生&#xff01; ♥️夕阳下&#xff0c;是最美的绽放&#xff0…

走进哈希心房

目录 哈希的概念 哈希函数 哈希冲突和解决方法 闭散列 插入 查找 删除 开散列 插入 查找 删除 哈希表&#xff08;开散列&#xff09;整体代码 位图 位图模拟实现思路分析&#xff1a; 位图应用 布隆过滤器 本文介绍unordered系列的关联式容器&#xff0c;unor…

安卓手机也可以使用新必应NewBing

没有魔法安卓手机也可以使用新必应NewBing 目前知道的是安卓手机 安卓手机先安装一个猴狐浏览器 打开手机自带浏览器&#xff0c;搜索关键词&#xff1a;猴狐浏览器&#xff0c;找到官网 也可以直接复制这个网址 狐猴浏览器 lemurbrowser CoolAPK 我的手机是荣耀安卓手机…

【正点原子FPGA连载】 第三十三章基于lwip的tftp server实验 摘自【正点原子】DFZU2EG_4EV MPSoC之嵌入式Vitis开发指南

第三十三章基于lwip的tftp server实验 文件传输是网络环境中的一项基本应用&#xff0c;其作用是将一台电子设备中的文件传输到另一台可能相距很远的电子设备中。TFTP作为TCP/IP协议族中的一个用来在客户机与服务器之间进行文件传输的协议&#xff0c;常用于无盘工作站、路由器…

「ML 实践篇」分类系统:图片数字识别

目的&#xff1a;使用 MNIST 数据集&#xff0c;建立数字图像识别模型&#xff0c;识别任意图像中的数字&#xff1b; 文章目录1. 数据准备&#xff08;MNIST&#xff09;2. 二元分类器&#xff08;SGD&#xff09;3. 性能测试1. 交叉验证2. 混淆矩阵3. 查准率与查全率4. P-R 曲…

2023年腾讯云服务器配置价格表(轻量服务器、CVM云服务器、GPU云服务器)

目前腾讯云服务器分为轻量应用服务器、云服务器云服务器云服务器CVM和GPU云服务器&#xff0c;首先介绍一下这三种服务。 1、腾讯云云服务器&#xff08;Cloud Virtual Machine&#xff0c;CVM&#xff09;提供安全可靠的弹性计算服务。 您可以实时扩展或缩减计算资源&#xff…

【经验总结】10年的嵌入式开发老手,到底是如何快速学习和使用RT-Thread的?(文末赠书5本)

【经验总结】一位近10年的嵌入式开发老手&#xff0c;到底是如何快速学习和使用RT-Thread的&#xff1f; RT-Thread绝对可以称得上国内优秀且排名靠前的操作系统&#xff0c;在嵌入式IoT领域一直享有盛名。近些年&#xff0c;物联网产业的大热&#xff0c;更是直接将RT-Thread这…

python绘制图像中心坐标二维分布曲线

数据和代码如下所示&#xff1a; import pandas as pd import numpy as np import matplotlib.pyplot as plt import xlrd from scipy.stats import multivariate_normal from mpl_toolkits.mplot3d import Axes3D np.set_printoptions(suppressTrue)# 根据均值、标准差,求指定…

SuperMap iMobile for Android 地图开发(一)

第一步&#xff1a;创建 Android Studio 项目 第一步&#xff1a;创建 Android Studio 项目 Android Studio 有两种创建项目的方法。 第一种是在 Android Studio起始页选择“Start a new Android Studio Project”。 第二种是在 Android Studio 主页选择“File”–>“New P…

数仓建模—主题域和主题

主题域和主题 前面在这个专题的第一篇,也就是数仓建模—数仓初识中我们就提到了一个概念—主题,这个概念其实在数仓的定义中也有提到 数据仓库是一个面向主题的、集成的、相对稳定的、反映历史变化的数据集合,用于支持管理决策。 今天我们主要来探究一下,数仓的主题到底是…

Multi-Camera Color Correction via Hybrid Histogram Matching直方图映射

文章目录Multi-Camera Color Correction via Hybrid Histogram Matching1. 计算直方图&#xff0c; 累计直方图&#xff0c; 直方图均衡化2. 直方图规定化&#xff0c;直方图映射。3. 实验环节3.1 输入图像3.2 均衡化效果3.3 映射效果4. 针对3实验环节的伪影 做处理和优化&…

ChatGPT研究分析:GPT-4做了什么

前脚刚研究了一轮GPT3.5&#xff0c;OpenAI很快就升级了GPT-4&#xff0c;整体表现有进一步提升。追赶一下潮流&#xff0c;研究研究GPT-4干了啥。本文内容全部源于对OpenAI公开的技术报告的解读&#xff0c;通篇以PR效果为主&#xff0c;实际内容不多。主要强调的工作&#xf…

九种跨域方式实现原理(完整版)

前言 前后端数据交互经常会碰到请求跨域&#xff0c;什么是跨域&#xff0c;以及有哪几种跨域方式&#xff0c;这是本文要探讨的内容。 一、什么是跨域&#xff1f; 1.什么是同源策略及其限制内容&#xff1f; 同源策略是一种约定&#xff0c;它是浏览器最核心也最基本的安…
最新文章