二分查找和斐波那契查找

这里写自定义目录标题

  • 二分查找
  • 斐波那契查找
  • 二分查找改进B
  • 二分查找改进C

二分查找

int binSearch(int* arr, int lo, int hi,int target)
{
	while (lo < hi){
	int mid = lo + ((hi - lo) >> 1);
	if (arr[mid] > target) hi = mid;
	else if (arr[mid] < target) lo = mid + 1;
	else  return mid;
	}
	return -1;
}

通过选择中点,不断迭代

斐波那契查找

与二分查找思想一致,划分点选取不一样
二分查早的话,一次迭代有三种情况,
中点值和目标值进行 > 比较后,满足则进入左半区间,
不满足,进入 < 比较,满足则进入右半区间,
不满足,则相等,返回

所以这样的话,想进入左半区间,进行一次比较,想进入右半区间,会进行两次比较,右侧比较会多
所以改进方法:调整左、右区域的宽度,适当地加长(缩短)左(右)子向量

class Fib {
private:
	int fibNumber;
	int Rank;
	int* arr;
public:
	Fib(int n)
	{
		this->fibNumber = n + 1;
		this->arr = new int[this->fibNumber];
		for (int i = 0; i < this->fibNumber; i++) {
			arr[i] = fib(i);
			this->Rank = i;
		}
	}
	int fib(int n)
	{
		int f = 0, g = 1;
		while (n-- > 0) {
			g += f; f = g - f;
		}
		return f;
	}
	~Fib() 
	{
		if (arr != NULL)
			delete[] arr;
		arr = NULL;
	}

	int get() { return this->arr[this->Rank]; }
	void prev() { this->Rank--; }

};


Fib为斐波那契类,构造函数为创建一个0到n的斐波那契数列,总共n+1项
get()函数为返回当前索引的斐波那契数
prev()函数为索引向前移动一项,即前一项的斐波那契数。


int fibSearch(int* arr, int lo, int hi, int target)
{
	Fib fib(hi - lo);
	while (lo < hi)
	{
		while (hi - lo  < fib.get()) fib.prev();
		int mid = lo + fib.get() - 1;
		if (arr[mid] > target) hi = mid;
		else if (arr[mid] < target) lo = mid + 1;
		else return mid;
	}
	return -1;
}

先实例化一个Fib类,初始化为一个hi-lo个数的斐波那契数列,
假设目标数列即要进行二分查找的数列在lo到hi索引之间有n个数(左闭右开),则初始化的斐波那契数列也是n个数

while (hi - lo  < fib.get())

这个循环中的比较是为了找出fib(k-1),数列中总数为fib(k)-1
在这里插入图片描述

二分查找改进B

原二分法问题,左右方向不平衡
斐波那契查找改进其一,调整前、后区域的宽度,适当地加长(缩短)前(后)子向量
实际上还有另一更为直接的方法,即令以上两项的常系数同时等于
1。也就是说,无论朝哪个方向深入,都只需做1次元素的大小比较,其二,统一沿两个方向深入所需要执行的比较次数,比如都统一为一次

在每个切分点A[mi]
处,仅做一次元素比较。具体地,若目标元素小于A[mi],则深入前端子向量A[lo, mi)继续查
找;否则,深入后端子向量A[mi, hi)继续查找。

int binSearchB(int* arr, int lo, int hi, int target)
{
	while (hi-lo>1) {//区间长度不是缩短为0时退出循环,而是区间长度缩短为1时退出循环
		int mid = lo + ((hi - lo) >> 1);
		//if (arr[mid] > target) hi = mid;//hi这面是开区间
		//else  lo = mid;
		(arr[mid] > target) ? hi = mid : lo = mid;
	}
	/*if (arr[lo] == target)
		return lo;
	else return -1;*/
	return (arr[lo] == target) ? lo : -1;
}

二分查找改进C

在有序向量中的查找,遇到重复的元素时会返回秩最大的那个,上述查找无法实现这个功能,因此加以改进

int binSearchC(int* arr, int lo, int hi, int target)
{
	while (hi > lo) {//区间长度缩短为0时退出循环
		int mid = lo + ((hi - lo) >> 1);
		(arr[mid] > target) ? hi = mid : lo = mid + 1;
	}
	return --lo;
}

版本C与版本B的差异,主要有三点。
首先,只有当有效区间的宽度缩短至0(而不是1)时,查找方告终止。
另外,在每次转入后端分支时,子向量的左边界取作mi + 1而不是mi。
表面上看,后一调整存在风险,此时只能确定切分点arr[mid]>target ,“贸然”地将arr[mi]排除在进一步的查找范围之外,似乎可能因遗漏这些元素,而导致本应成功的查找以失败告终。
但其实没问题
在这里插入图片描述

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

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

相关文章

链路追踪系列-02.演示zipkin

当本机启动docker es zipkinServer之后&#xff1a; 启动3个项目&#xff1a;先eureka-server&#xff0c;再 PaymentMain8001,… 浏览器打开&#xff1a;http://localhost:9001/consumer/payment/zipkin consumer代码 &#xff1a; provider: 此时查询es:

html5——列表、表格

目录 列表 无序列表 有序列表 自定义列表 表格 基本结构 示例 表格的跨列 表格的跨行 列表 无序列表 <ul>【声明无序列表】 <li>河间驴肉火烧</li>【声明列表项】 <li>唐山棋子烧饼</li> <li>邯郸豆沫</li> <l…

香橙派AIpro:体验强劲算力,运行ROS系统

文章目录 前言一、香橙派AIpro开箱及功能介绍1.1香橙派AIpro开箱1.2香橙派AIpro功能介绍 二、香橙派AIpro资料下载及环境搭建2.1资料下载2.2环境搭建2.3使用串口启动进入开发板2.4使用HDMI线接入屏幕启动 三、部署ROS系统四、香橙派AIpro的使用和体验感受 前言 本篇文章将带体…

升级到LVGL9的一些变化(后续发现再补充)

目录 一、主要内容 二、新增内容 三、常规API变化 四、Display API(显示API) 五、其他 最近在将LVGL8的demo代码升级到LVGL9,带来不小的变化 ,收集网上的一些内容,整理如下: 一、主要内容 二、新增内容 三、常规API变化 四、Display API(显示API)

3.4、matlab实现SGM/BM/SAD立体匹配算法计算视差图

1、matlab实现SGM/BM/SAD立体匹配算法计算视差图简介 SGM&#xff08;Semi-Global Matching&#xff09;、BM&#xff08;Block Matching&#xff09;和SAD&#xff08;Sum of Absolute Differences&#xff09;都是用于计算立体匹配&#xff08;Stereo Matching&#xff09;的…

python基础语法 005 函数1-2 函数作用域

1 函数续 1.7 函数作用域 1.7.1 全局变量 定义在函数外部的变量全局变量在函数内部和函数外部都可以访问使用 a 100 def run():print("a {}".format(a))print(a) print(run())1.7.2 局部变量 函数是一个黑盒子&#xff0c;外面看不到盒子里面的东西&#xff0…

vue-router history 模式下将所有资源文件js/css/img都存放在oss 利用 cdn 访问整体思路汇总

背景 我们有一个域名https://example.com&#xff0c;但是ssl证书很贵&#xff0c;搞子域名来承接新站点有点费钱&#xff0c;所以我们想用一个目录https://example.com/admin/ 来作为管理后台的站点&#xff0c;这个站点是单页面应用&#xff0c;我又想让其用history router的…

AI为ToB企业节省大量隐性成本

前些天&#xff0c;在向朋友介绍“客户在哪儿AI”时&#xff0c;我着重说了它效果最为显著的两个功能&#xff0c;即&#xff0c;为ToB企业指明在哪儿能准确的找到客户和该场景下的最佳营销策略&#xff0c;以及深入洞察竞争对手并找到最佳竞争策略。 当我说完这两个核心功能的…

各向异性含水层中地下水三维流基本微分方程的推导(二)

各向异性含水层中地下水三维流基本微分方程的推导 参考文献&#xff1a; [1] 刘欣怡,付小莉.论连续性方程的推导及几种形式转换的方法[J].力学与实践,2023,45(02):469-474. 书接上回&#xff1a; 我们能得到三个方向的流入流出平衡方程&#xff1a; ∂ ρ u x ∂ x d x d y d…

YOWOv2(yowov2)动作识别+Fastreid身份识别 详细安装与实现

首先yowov2是一款简单且实时的时空动作检测方案&#xff0c;fastreid是行人重识别&#xff08;身份识别&#xff09; yowov2介绍链接直达fastreid链接直达为时空动作检测任务设计实时框架仍然是一个挑战。YOWOv2 提出了一种新颖的实时动作检测框架&#xff0c;利用三维骨干和二…

[web]-sql注入-白云搜索引擎

ctrlu查看源代码&#xff0c;发现前端有js过滤 <script>function myFunction(){var xdocument.getElementById("number").value;var adocument.getElementById("word").value;var ba.replace(/[\ |\~|\|\!|\|\#|\$|\%|\^|\&|\*|\(|\)|\-|\_|\|\…

如何写论文的讨论和结论部分,提升审稿通过率300%?(附例句模版)

我是娜姐 迪娜学姐 &#xff0c;一个SCI医学期刊编辑&#xff0c;探索用AI工具提效论文写作和发表。 关于论文讨论Discussion部分的撰写&#xff0c;娜姐之前写过几篇文章&#xff1a; 1 Discussion讨论部分被3个审稿人说没深度没逻辑&#xff0c;用这个AI工具三步拯救了我&am…

【ingress-nginx】安装配置及Helm工具安装

【ingress-nginx】安装配置及Helm工具安装 安装时候需要用到一个工具——Helm【相当于linux中的yum工具】。 一&#xff0c;Helm安装 官网&#xff1a;https://helm.sh/docs/intro/install # 下载 wget https://get.helm.sh/helm-v3.2.3-linux-amd64.tar.gz# 解压 tar -zxv…

78. UE5 RPG 创建技能数据并初始化技能ui

在上一篇文章里&#xff0c;我们创建了技能的UI&#xff0c;接下来&#xff0c;我们要考虑如何实现对技能UI的填充&#xff0c;肯定不能直接写死&#xff0c;需要有一些方法去实现技能的更新。我们期望能够创建一个技能数据&#xff0c;然后根据数据通过回调的方式实现数据的更…

免费的ssh工具

1.Quickstart - kitty 2 Download Termius for Windows 3. MobaXterm Xserver with SSH, telnet, RDP, VNC and X11 - Download

Qt MV架构-视图类

一、基本概念 在MV架构中&#xff0c;视图包含了模型中的数据项&#xff0c;并将它们呈现给用户。数据项的表示方法&#xff0c;可能和数据项在存储时用的数据结构完全不同。 这种内容与表现分离之所以能够实现&#xff0c;是因为使用了 QAbstractItemModel提供的一个标准模…

EasyExcel批量读取Excel文件数据导入到MySQL表中

1、EasyExcel简介 官网&#xff1a;EasyExcel官方文档 - 基于Java的Excel处理工具 | Easy Excel 官网 2、代码实战 首先引入jar包 <dependency><groupId>com.alibaba</groupId><artifactId>easyexcel</artifactId><version>3.3.2</v…

基于FPGA的千兆以太网设计(1)----大白话解释什么是以太网

1、什么是以太网? 还记得初学以太网的时候,我就被一大堆专业名词给整懵了:什么以太网,互联网,MAC,IP,局域网,万维网,网络分层模型等等等等。慢着!我学的不是以太网吗?怎么出来这么一大堆东西? 啊!以太网究竟是什么?别急,我接下来就尽量用通俗的大白话来给你解释…

Phpstudy 2018 之xhcms搭建

1、由于直接访问根目录无法进入网站 2、所以采用搭建网站&#xff0c;第一使用系统服务模式、选择php-5.4.45Apache模式 3、网站域名为本地ip地址或者127.0.0.1、端口8085 4、浏览器输入127.0.0.1:8085直接转到系统安装 5、返回输入127.0.0.1:8085&#xff0c;成功进入网站

前端JS特效第36波:jQ多种相册切换效果

jQ多种相册切换效果&#xff0c;先来看看效果&#xff1a; 部分核心的代码如下&#xff1a; <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns"h…