减治法思想-二分查找图解案例

2024-06-14 06:44

本文主要是介绍减治法思想-二分查找图解案例,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

减治法介绍

减治法思想

​ 分治法是将一个大问题划分为若干个子问题,分别求各个子问题,然后把子问题的解进行合并得到原问题的解。

​ 减治法同样是把一个大问题划分为若干个子问题,但是并不是求解所有的子问题,因为原问题的解就在其中一个子问题当中,所以只求解其中一个子问题。

​ 与分治法不同的就在于这个“减”字上,会不断的将原问题的规模减小,直到找到最终的解。

减治法求解过程:

​ 减治法将原问题分解为若干个子问题,并且原问题(规模为n)的解和子问题(规模为 n/2 或 n-1)的解之间存在某种确定的关系:

​ 原问题的解只存在其中一个子问题中。

​ 原问题的解与其中一个子问题的解之间存在某种对应关系。

那么求解过程就可以确定了:

  1. 将原问题分解为规模较小的子问题
  2. 找到原问题的解所在的子问题
  3. 重复第1、2步直到得到子问题的解
  4. 根据子问题的解,直接得出或计算出原问题的解。

​ 前面蛮力法中使用的案例选择排序其实也是一种减治法,因为其每次都会去除掉一个元素,使问题的规模减一。

减治法案例-二分查找

分析:

​ 二分查找每次计算完数组中间值,与待查找元素对比之后,会使下一次待查找的区间减半,所以二分查找属于比较经典的减治。

过程如下:

  1. 取有序序列的中间值与待查找值比较。
  2. 若中间值与待查找值相同则查找成功。
  3. 若中间值比待查找值小,则在中间记录的左边区间查找。
  4. 若中间值比待查找值大,则在中间记录的右边区间查找。
  5. 重复上述1~4过程,直到查找成功或区间无记录。

过程图解:

1、初始化

​ 有序数组:{ -1、0、3、9、11、13、22、27、55、57、60、77 }

​ 待查找元素: 33

​ 初始化:左下标为0(left = 0)、右下标为11(right=11)
在这里插入图片描述

2、第一趟比较

计算中间值:

m i d = l e f t + ( r i g h t − l e f t ) / 2 = 0 + ( 11 − 0 ) / 2 = 5 mid = left + (right - left) / 2 = 0 + (11 - 0) / 2 = 5 mid=left+(rightleft)/2=0+(110)/2=5

减少规模:

n u m s [ 5 ] = 13 < 33 nums[5] = 13 < 33 nums[5]=13<33,带查找值在数组右半区,则 l e f t = m i d + 1 = 5 + 1 = 6 left = mid + 1 = 5 + 1 = 6 left=mid+1=5+1=6

在这里插入图片描述

3、第二躺比较

计算中间值:

m i d = l e f t + ( r i g h t − l e f t ) / 2 = 6 + ( 11 − 6 ) / 2 = 8 mid = left + (right - left) / 2 = 6 + (11 - 6) / 2 = 8 mid=left+(rightleft)/2=6+(116)/2=8

得到结果:

n u m s [ 8 ] = 33 = 33 nums[8] = 33 = 33 nums[8]=33=33,找到带查找值在数组中的下标8,查找结束。

在这里插入图片描述

代码实现:

    public static int execute(int[] data, int key) {int leftIndex = 0, rightIndex = data.length - 1;int midIndex = -1;// 当左下标不再小于右下标,说明区间内已经没有元素,即数组内没有待查找元素while (leftIndex < rightIndex) {midIndex = (rightIndex - leftIndex) / 2 + leftIndex;// 找到就直接返回if (data[midIndex] == key) {return midIndex;//中间值小于待查找值,待查找值在数组右半区域} else if (data[midIndex] < key) {leftIndex = midIndex + 1;//中间值大于待查找值,待查找值在数组左半区域} else {rightIndex = midIndex - 1;}}return data[midIndex] == key ? midIndex : -1;}

这篇关于减治法思想-二分查找图解案例的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1059664

相关文章

Python Transformers库(NLP处理库)案例代码讲解

《PythonTransformers库(NLP处理库)案例代码讲解》本文介绍transformers库的全面讲解,包含基础知识、高级用法、案例代码及学习路径,内容经过组织,适合不同阶段的学习者,对... 目录一、基础知识1. Transformers 库简介2. 安装与环境配置3. 快速上手示例二、核心模

Python中使用正则表达式精准匹配IP地址的案例

《Python中使用正则表达式精准匹配IP地址的案例》Python的正则表达式(re模块)是完成这个任务的利器,但你知道怎么写才能准确匹配各种合法的IP地址吗,今天我们就来详细探讨这个问题,感兴趣的朋... 目录为什么需要IP正则表达式?IP地址的基本结构基础正则表达式写法精确匹配0-255的数字验证IP地

MySQL高级查询之JOIN、子查询、窗口函数实际案例

《MySQL高级查询之JOIN、子查询、窗口函数实际案例》:本文主要介绍MySQL高级查询之JOIN、子查询、窗口函数实际案例的相关资料,JOIN用于多表关联查询,子查询用于数据筛选和过滤,窗口函... 目录前言1. JOIN(连接查询)1.1 内连接(INNER JOIN)1.2 左连接(LEFT JOI

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

MySQL中实现多表查询的操作方法(配sql+实操图+案例巩固 通俗易懂版)

《MySQL中实现多表查询的操作方法(配sql+实操图+案例巩固通俗易懂版)》本文主要讲解了MySQL中的多表查询,包括子查询、笛卡尔积、自连接、多表查询的实现方法以及多列子查询等,通过实际例子和操... 目录复合查询1. 回顾查询基本操作group by 分组having1. 显示部门号为10的部门名,员

Windows系统下如何查找JDK的安装路径

《Windows系统下如何查找JDK的安装路径》:本文主要介绍Windows系统下如何查找JDK的安装路径,文中介绍了三种方法,分别是通过命令行检查、使用verbose选项查找jre目录、以及查看... 目录一、确认是否安装了JDK二、查找路径三、另外一种方式如果很久之前安装了JDK,或者在别人的电脑上,想

Python爬虫selenium验证之中文识别点选+图片验证码案例(最新推荐)

《Python爬虫selenium验证之中文识别点选+图片验证码案例(最新推荐)》本文介绍了如何使用Python和Selenium结合ddddocr库实现图片验证码的识别和点击功能,感兴趣的朋友一起看... 目录1.获取图片2.目标识别3.背景坐标识别3.1 ddddocr3.2 打码平台4.坐标点击5.图

使用Navicat工具比对两个数据库所有表结构的差异案例详解

《使用Navicat工具比对两个数据库所有表结构的差异案例详解》:本文主要介绍如何使用Navicat工具对比两个数据库test_old和test_new,并生成相应的DDLSQL语句,以便将te... 目录概要案例一、如图两个数据库test_old和test_new进行比较:二、开始比较总结概要公司存在多

SpringBoot实现动态插拔的AOP的完整案例

《SpringBoot实现动态插拔的AOP的完整案例》在现代软件开发中,面向切面编程(AOP)是一种非常重要的技术,能够有效实现日志记录、安全控制、性能监控等横切关注点的分离,在传统的AOP实现中,切... 目录引言一、AOP 概述1.1 什么是 AOP1.2 AOP 的典型应用场景1.3 为什么需要动态插

Golang操作DuckDB实战案例分享

《Golang操作DuckDB实战案例分享》DuckDB是一个嵌入式SQL数据库引擎,它与众所周知的SQLite非常相似,但它是为olap风格的工作负载设计的,DuckDB支持各种数据类型和SQL特性... 目录DuckDB的主要优点环境准备初始化表和数据查询单行或多行错误处理和事务完整代码最后总结Duck