突破编程_C++_查找算法(二分查找)

news/2024/5/26 19:40:19/文章来源:https://blog.csdn.net/h8062651/article/details/136681050

1 算法题 :使用二分查找算法在有序数组中查找指定元素

1.1 题目含义

给定一个升序排列的整数数组 nums 和一个目标值 target,写一个函数来搜索 nums 中的 target,如果目标值存在于数组中,则返回它的索引;否则返回 -1。你必须使用二分查找算法来解决这个问题。

二分查找算法是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。

1.2 示例

示例 1:
输入:

  • nums = [-1, 0, 3, 5, 9, 12]
  • target = 9

输出:

  • 4

说明:

  • 9 存在于 nums 中,且其索引为 4。

示例 2:
输入:

  • nums = [-1, 0, 3, 5, 9, 12]
  • target = 2

输出:

  • -1

说明:

  • 2 不存在于 nums 中,返回 -1。

示例 3:
输入:

  • nums = []
  • target = 0

输出:

  • -1

说明:

  • nums 为空,0 不存在于 nums 中,返回 -1。

2 解题思路

2.1 循环遍历实现

(1)初始化指针:

  • 设定三个指针,start 指向数组的开始位置,end 指向数组的结束位置,mid 用于计算当前查找区间的中间位置。

(2)计算中间位置:

  • 根据 start 和 end 的位置,计算出当前查找区间的中间位置 mid。这里要注意防止整数溢出,所以可以使用 (start + end) / 2 的方式来计算。

(3)比较与目标值:

  • 将 mid 位置的元素与目标值进行比较。

(4)调整查找区间:

  • 如果 mid 位置的元素等于目标值,则查找成功,直接返回 mid。
  • 如果 mid 位置的元素大于目标值,说明目标值(如果存在)只可能出现在 mid 的左侧,因此更新 end 为 mid - 1。
  • 如果 mid 位置的元素小于目标值,说明目标值(如果存在)只可能出现在 mid 的右侧,因此更新 start 为 mid + 1。

(5)循环判断:

  • 重复步骤 2 至步骤 4,直到 start 大于 end,这意味着整个查找区间已经被遍历完,且没有找到目标值。

(6)返回结果:

  • 如果循环结束仍然没有找到目标值,则返回 -1 表示查找失败。

2.2 递归实现

使用递归实现二分查找的解题思路如下:

首先,需要明确递归的基本思想:将问题分解为更小的子问题,直到子问题可以直接解决。在二分查找中,每次都将搜索范围划分为两部分,并递归地在其中一部分中继续查找,直到找到目标值或确定目标值不存在。

(1)定义递归函数:

  • 定义一个递归函数,该函数接收一个有序数组、目标值、当前搜索范围的起始位置 start 和结束位置 end 作为参数。

(2)递归终止条件:

  • 当 start 大于 end 时,表示当前搜索范围为空,即目标值不在数组中,递归终止,返回 -1。

(3)计算中间位置:

  • 在递归函数中,计算当前搜索范围的中间位置 mid。

(4)比较与目标值:

  • 将 mid 位置的元素与目标值进行比较。

(5)递归调用:

  • 如果 mid 位置的元素等于目标值,则递归终止,返回 mid。
  • 如果 mid 位置的元素大于目标值,说明目标值(如果存在)只可能出现在 mid 的左侧,因此递归调用函数,传入新的搜索范围(start,mid - 1)。
  • 如果 mid 位置的元素小于目标值,说明目标值(如果存在)只可能出现在 mid 的右侧,因此递归调用函数,传入新的搜索范围(mid + 1,end)。

(6)返回结果:

  • 递归调用的结果即为最终的查找结果,将其返回。

这个递归过程会一直进行下去,直到找到目标值或确定目标值不在数组中。递归实现方式使得代码更加简洁和清晰,但需要注意递归深度的问题,避免因为递归过深而导致栈溢出。在实际应用中,如果数组规模很大,建议使用循环遍历实现来避免这个问题。

3 算法实现代码

3.1 循环遍历实现

如下为算法实现代码:

#include <iostream>  
#include <string>  
#include <vector>  class Solution
{
public:int binarySearch(std::vector<int>& nums, int target) {int start = 0;int end = nums.size() - 1;while (start <= end) {int mid = start + (end - start) / 2; // 防止溢出  if (nums[mid] == target) {// 找到目标值,返回其索引  return mid;}else if (nums[mid] < target) {// 目标值在mid右侧,更新start  start = mid + 1;}else {// 目标值在mid左侧,更新end  end = mid - 1;}}// 没有找到目标值  return -1;}
};

这段代码中定义了一个名为 binarySearch 的成员函数,它接受一个整数向量 nums 和一个目标值 target 作为参数。函数内部使用 start 和 end 变量来追踪当前搜索范围的左右边界,并通过计算中间位置 mid 来确定接下来搜索哪一部分。根据 mid 位置的元素与目标值的比较结果,更新 start 或 end 的值来缩小搜索范围。当 start 大于 end 时,表示搜索区间已被遍历完,此时返回 -1 表示未找到目标值。如果找到目标值,则返回其索引。

调用上面的算法,并得到输出:

int main() 
{Solution s;std::vector<int> nums = { -1, 0, 3, 5, 9, 12 };int target = 9;int result = s.binarySearch(nums, target);if (result != -1) {std::cout << "Target found at index: " << result << std::endl;}else {std::cout << "Target not found in the array." << std::endl;}return 0;
}

上面代码的输出为:

Target found at index: 4

3.2 递归实现

如下为算法实现代码:

#include <iostream>  
#include <string>  
#include <vector>  class Solution
{
public:int binarySearch(std::vector<int>& nums, int target) {		return binarySearchRecursive(nums, target, 0, nums.size() - 1);}private:int binarySearchRecursive(const std::vector<int>& nums, int target, int start, int end) {// 递归终止条件  if (start > end) {return -1; // 目标值不在数组中  }int mid = start + (end - start) / 2; // 防止溢出  // 检查是否找到目标值  if (nums[mid] == target) {return mid;}// 递归调用:目标值在左半部分  if (nums[mid] > target) {return binarySearchRecursive(nums, target, start, mid - 1);}// 递归调用:目标值在右半部分  return binarySearchRecursive(nums, target, mid + 1, end);}
};

这段代码中定义了一个名为 binarySearchRecursive 的私有递归成员函数,它接受一个整数向量 nums、一个目标值 target、以及当前搜索范围的起始位置 start 和结束位置 end 作为参数。
函数内部首先检查递归终止条件,即 start 是否大于 end,如果是,则返回 -1 表示未找到目标值。接着,计算中间位置 mid,然后与目标值进行比较。如果 mid 位置的元素等于目标值,则直接返回 mid。否则,根据比较结果递归地在左半部分或右半部分继续查找。递归调用会一直进行下去,直到找到目标值或搜索范围为空。

4 测试用例

以下是针对上面算法的测试用例,基本覆盖了各种情况:

(1)基础测试用例
输入:数组 [-1, 0, 3, 5, 9, 12],目标值 9
输出:4
说明:目标值 9 存在于数组中,位于索引 4 的位置。

(2)目标值不存在于数组中
输入:数组 [-1, 0, 3, 5, 9, 12],目标值 2
输出:-1
说明:目标值 2 不存在于数组中。

(3)目标值位于数组开头
输入:数组 [-1, 0, 3, 5, 9, 12],目标值 -1
输出:0
说明:目标值 -1 位于数组的开头,即索引 0 的位置。

(4)目标值位于数组末尾
输入:数组 [-1, 0, 3, 5, 9, 12],目标值 12
输出:5
说明:目标值 12 位于数组的末尾,即索引 5 的位置。

(5)目标值位于数组中间
输入:数组 [-1, 0, 3, 5, 9, 12],目标值 3
输出:2
说明:目标值 3 位于数组的中间位置,即索引 2 的位置。

(6)空数组
输入:数组 [],目标值 9
输出:-1
说明:空数组不包含任何元素,因此无法找到目标值。

(7)数组只有一个元素
输入:数组 [9],目标值 9
输出:0
说明:数组只有一个元素,且该元素就是目标值,位于索引 0 的位置。

(8)数组中存在多个相同的目标值
输入:数组 [1, 2, 3, 3, 4, 5],目标值 3
输出:2 或 3
说明:数组中存在多个目标值 3,返回任意一个目标值的索引都是正确的。这里可以返回 2 或 3。

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

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

相关文章

C#,数值计算,希尔伯特矩阵(Hilbert Matrix)的算法与源代码

Hilbert, David (1862-1943) 1 希尔伯特(Hilbert) 德国数学家,在《几何学基础》中提出了第一套严格的几何公理(1899年)。他还证明了自己的系统是自洽的。他发明了一条简单的空间填充曲线,即埃里克魏斯汀的数学世界,即希尔伯特曲线,埃里克魏斯汀的数学世界,并证明了不…

Unity资源热更新----AssetBundle

13.1 资源热更新——AssetBundle1-1_哔哩哔哩_bilibili Resources 性能消耗较大 Resources文件夹大小不能超过2个G 获取AssetBundle中的资源 打包流程 选择图片后点击 创建文件夹&#xff0c;Editor优先编译 打包文件夹位置 using UnityEditor; using UnityEngine; public cla…

v-model 粗略解析

v-model 粗略解析 v-model是什么&#xff1f; 双向数据绑定&#xff0c;可以从data流向页面&#xff0c;也可以从页面流向data通常用于表单收集&#xff0c;v-model 默认绑定 value 值书写形式&#xff1a; v-model:value"" 或 v-model v-model原理是什么&#xf…

C#快速入门基础

本篇文章从最基础的C#编程开始学习&#xff0c;经过非常优秀的面向对象编程思想和方法的学习&#xff0c;为C#编程打下基础。 第 01 章 C#开发环境之VS使用和.NET平台基础 1.1 Visual Studio 开发环境 1.1.1 硬件环境 i5CPUi5CPU&#xff08;建议 4核 4线程或以上 &#xff0…

WebMagic框架

1.webmagic框架 webmagic框架是一个Java实现的爬虫框架&#xff0c;底层依然是HttpClient和jsoup 组件&#xff1a; downloader&#xff1a;下载器组件PageProcessor&#xff1a;页面解析组件&#xff08;必须自定义&#xff09;scheculer&#xff1a;访问队列组件pipeline&am…

Excel数据转sql、json、html

1.Excel转Sql 利用Excel公式CONCATENATE可以实现“insert into table values(”与单元格A1的值拼接&#xff0c;这样一句insert语句就组合好了。 Excel数据&#xff1a; 完整公式&#xff1a; CONCATENATE("INSERT INTO volume(item, volume,update_time) VALUES("…

【测试】构建质量保证之路:编写测试用例的艺术

&#x1f34e;个人博客&#xff1a;个人主页 &#x1f3c6;个人专栏&#xff1a;Linux ⛳️ 功不唐捐&#xff0c;玉汝于成 目录 前言 正文 1. 确定测试目标&#xff1a; 2. 理解需求和规格&#xff1a; 3. 确定测试条件&#xff1a; 4. 编写测试用例&#xff1a; 结…

drone ci 是什么

Drone CI是一个开源的持续集成和持续部署&#xff08;CI/CD&#xff09;系统&#xff0c;它使用Docker容器技术自动化软件的构建、测试和部署过程。Drone的设计哲学是简单和易用&#xff0c;通过使用Docker容器&#xff0c;它可以很容易地创建隔离的环境来运行测试和部署任务&a…

【Algorithms 4】算法(第4版)学习笔记 17 - 4.3 最小生成树

文章目录 前言参考目录学习笔记1&#xff1a;介绍1.1&#xff1a;定义1.2&#xff1a;应用2&#xff1a;贪心算法 greedy algorithm2.1&#xff1a;简化假设2.2&#xff1a;切分定理2.3&#xff1a;demo 演示2.4&#xff1a;贪心算法的证明2.5&#xff1a;算法实现简要说明2.6&…

数据结构:图及相关算法讲解

图 1.图的基本概念2. 图的存储结构2.1邻接矩阵2.2邻接表2.3两种实现的比较 3.图的遍历3.1 图的广度优先遍历3.2 图的深度优先遍历 4.最小生成树4.1 Kruskal算法4.2 Prim算法4.3 两个算法比较 5.最短路径5.1两个抽象存储5.2单源最短路径--Dijkstra算法5.3单源最短路径--Bellman-…

Python Excel 文本编辑库之xlsxwriter使用详解

概要 在现代数据处理和报表生成中,Excel 文件是一个非常常见的格式。Python XlsxWriter 库是一个强大的工具,可以帮助开发者轻松创建和编辑 Excel 文件,并且具有高度的灵活性和可定制性。本文将全面介绍 XlsxWriter 库的原理、功能、用法,并通过丰富的示例代码来展示其强大…

C++ 作业 24/3/13

1、设计一个Per类&#xff0c;类中包含私有成员:姓名、年龄、指针成员身高、体重&#xff0c;再设计一个Stu类&#xff0c;类中包含私有成员:成绩、Per类对象p1&#xff0c;设计这两个类的构造函数、析构函数和拷贝构造函数。 #include <iostream>using namespace std;c…

【老旧小区用电安全谁能管?】安科瑞智慧用电安全管理系统解决方案

行业背景 电气火灾指由电气故障引发的火灾。每年以30%的比例高居各类火灾原因之首。以50%到80%的比例高居重特大火灾之首。已成为业界重点关注的对象并为此进行着孜孜不倦的努力。 国务院安委会也于2017年5月至2020年4月年开展了为期3年的电气火灾综合治理工作。在各界努力的…

微信小程序之vue按钮切换内容变化

效果图如下&#xff1b; 上代码 <template><view class"content"><view class"searchDiv"><view class"paytab"><view class"buttab" v-for"(t,index) in tabList" :key"index" clic…

Address already in dse_JVM_Bind。端口莫名被占用【占用8080端口!!!】

文章目录 问题描述&#xff1a;Address already in dse:JVM_Bind问题可能的原因解决方案 问题描述&#xff1a;Address already in dse:JVM_Bind 问题可能的原因 当前端口已经有别的程序在占用着 我曾经被QQ占用过8080端口&#xff0c;Oracle启动了OracleHttp服务会占用8080端…

接口自动化框架(Pytest+request+Allure)

前言&#xff1a; 接口自动化是指模拟程序接口层面的自动化&#xff0c;由于接口不易变更&#xff0c;维护成本更小&#xff0c;所以深受各大公司的喜爱。 接口自动化包含2个部分&#xff0c;功能性的接口自动化测试和并发接口自动化测试。 本次文章着重介绍第一种&#xff0c…

InstantID Zero-shot Identity-Preserving Generation in Seconds

InstantID: Zero-shot Identity-Preserving Generation in Seconds TL; DR&#xff1a;InstantID IP-Adapter (Face) ControlNet&#xff0c;实现了具有较高保真度的人脸 ID 生成。 方法 InstantID 想做到的事情是&#xff1a;给定一张参考人脸 ID 图片&#xff0c;生成该…

*地宫取宝c++

题目 输入样例1&#xff1a; 2 2 2 1 2 2 1输出样例1&#xff1a; 2输入样例2&#xff1a; 2 3 2 1 2 3 2 1 5输出样例2&#xff1a; 14 思路 题目说从入口开始&#xff0c;只能向右或向下行走到达右下角&#xff0c;类似“摘花生”这道题的模型。题目又说只有当格子里的宝…

C语言中如何进行内存管理

主页&#xff1a;17_Kevin-CSDN博客 收录专栏&#xff1a;《C语言》 C语言是一种强大而灵活的编程语言&#xff0c;但与其他高级语言不同&#xff0c;它要求程序员自己负责内存的管理。正确的内存管理对于程序的性能和稳定性至关重要。 一、引言 C 语言是一门广泛使用的编程语…

Flink概述

1.什么是Flink 是一个框架和分布式处理引擎&#xff0c;用于对无界和有界数据流进行有状态计算。 官网&#xff1a;Flink 2.Flink的发展历史 Flink起源于一个叫作Stratosphere的项目&#xff0c;它是由3所地处柏林的大学和欧洲其他一些大学在2010~2014年共同进行的研究项目&a…