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

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

相关文章

PostgreSQL的扩展dict_int应用案例解析

《PostgreSQL的扩展dict_int应用案例解析》dict_int扩展为PostgreSQL提供了专业的整数文本处理能力,特别适合需要精确处理数字内容的搜索场景,本文给大家介绍PostgreS... 目录PostgreSQL的扩展dict_int一、扩展概述二、核心功能三、安装与启用四、字典配置方法

MySQL中查找重复值的实现

《MySQL中查找重复值的实现》查找重复值是一项常见需求,比如在数据清理、数据分析、数据质量检查等场景下,我们常常需要找出表中某列或多列的重复值,具有一定的参考价值,感兴趣的可以了解一下... 目录技术背景实现步骤方法一:使用GROUP BY和HAVING子句方法二:仅返回重复值方法三:返回完整记录方法四:

Python中re模块结合正则表达式的实际应用案例

《Python中re模块结合正则表达式的实际应用案例》Python中的re模块是用于处理正则表达式的强大工具,正则表达式是一种用来匹配字符串的模式,它可以在文本中搜索和匹配特定的字符串模式,这篇文章主... 目录前言re模块常用函数一、查看文本中是否包含 A 或 B 字符串二、替换多个关键词为统一格式三、提

Python get()函数用法案例详解

《Pythonget()函数用法案例详解》在Python中,get()是字典(dict)类型的内置方法,用于安全地获取字典中指定键对应的值,它的核心作用是避免因访问不存在的键而引发KeyError错... 目录简介基本语法一、用法二、案例:安全访问未知键三、案例:配置参数默认值简介python是一种高级编

MySQL中的索引结构和分类实战案例详解

《MySQL中的索引结构和分类实战案例详解》本文详解MySQL索引结构与分类,涵盖B树、B+树、哈希及全文索引,分析其原理与优劣势,并结合实战案例探讨创建、管理及优化技巧,助力提升查询性能,感兴趣的朋... 目录一、索引概述1.1 索引的定义与作用1.2 索引的基本原理二、索引结构详解2.1 B树索引2.2

从入门到精通MySQL 数据库索引(实战案例)

《从入门到精通MySQL数据库索引(实战案例)》索引是数据库的目录,提升查询速度,主要类型包括BTree、Hash、全文、空间索引,需根据场景选择,建议用于高频查询、关联字段、排序等,避免重复率高或... 目录一、索引是什么?能干嘛?核心作用:二、索引的 4 种主要类型(附通俗例子)1. BTree 索引(

HTML中meta标签的常见使用案例(示例详解)

《HTML中meta标签的常见使用案例(示例详解)》HTMLmeta标签用于提供文档元数据,涵盖字符编码、SEO优化、社交媒体集成、移动设备适配、浏览器控制及安全隐私设置,优化页面显示与搜索引擎索引... 目录html中meta标签的常见使用案例一、基础功能二、搜索引擎优化(seo)三、社交媒体集成四、移动

六个案例搞懂mysql间隙锁

《六个案例搞懂mysql间隙锁》MySQL中的间隙是指索引中两个索引键之间的空间,间隙锁用于防止范围查询期间的幻读,本文主要介绍了六个案例搞懂mysql间隙锁,具有一定的参考价值,感兴趣的可以了解一下... 目录概念解释间隙锁详解间隙锁触发条件间隙锁加锁规则案例演示案例一:唯一索引等值锁定存在的数据案例二:

C++作用域和标识符查找规则详解

《C++作用域和标识符查找规则详解》在C++中,作用域(Scope)和标识符查找(IdentifierLookup)是理解代码行为的重要概念,本文将详细介绍这些规则,并通过实例来说明它们的工作原理,需... 目录作用域标识符查找规则1. 普通查找(Ordinary Lookup)2. 限定查找(Qualif

MySQL 表的内外连接案例详解

《MySQL表的内外连接案例详解》本文给大家介绍MySQL表的内外连接,结合实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录表的内外连接(重点)内连接外连接表的内外连接(重点)内连接内连接实际上就是利用where子句对两种表形成的笛卡儿积进行筛选,我