为什么递归的二进制搜索有时会导致一些而不是所有不存在的输入的堆栈溢出？

递归的二进制搜索有时会导致一些而不是所有不存在的输入的堆栈溢出，原因如下：

递归的二进制搜索算法是一种通过将搜索空间逐渐缩小一半来寻找目标元素的方法。它将搜索范围一分为二，然后根据目标值与中间值的大小关系，确定继续搜索的方向。如果目标值小于中间值，则继续在左半部分搜索；如果目标值大于中间值，则继续在右半部分搜索；如果目标值等于中间值，则找到目标元素。

当搜索的目标元素不存在时，递归的二进制搜索会在每次划分搜索空间之后继续对剩余部分进行递归调用。每次递归调用都会将搜索空间缩小一半，直到搜索空间为空或找到目标元素为止。

然而，当目标元素不存在时，递归的二进制搜索会不断划分搜索空间，最终将搜索空间缩小到只剩下一个元素。此时，如果继续进行递归调用，就会导致堆栈溢出。

堆栈溢出的原因是每次递归调用会在堆栈中创建一个新的函数调用帧，用于保存函数的局部变量、返回地址等信息。由于递归的二进制搜索会不断进行递归调用，导致堆栈中的函数调用帧数量过多，超出了堆栈的容量限制，从而导致堆栈溢出。

为了避免递归的二进制搜索导致堆栈溢出，可以采取以下几种方法：

使用非递归的二进制搜索算法，利用循环来替代递归调用，可以避免堆栈溢出的问题。
在递归调用之前，添加对搜索空间是否为空的判断，当搜索空间为空时，立即结束递归调用，避免不必要的递归操作。
当目标元素不存在时，可以通过返回特定的值或抛出异常来表示搜索失败，而不是继续进行递归调用。

腾讯云相关产品：

腾讯云函数（云原生）：https://cloud.tencent.com/product/scf
腾讯云搜索（文本搜索服务）：https://cloud.tencent.com/product/css
腾讯云堆栈（弹性Web托管）：https://cloud.tencent.com/product/tiw

相关·内容

数据结构与算法 --- 递归（二）

引言上文数据结构与算法 --- 递归（一）讲述了什么是递归算法，如何编写递归算法及如何写好递归算法，本文着重讲述一下如何避免递归过深导致的堆栈溢出问题。...递归的过程包含大量的函数调用，如果递归求解的数据规模很大，函数调用层次很深，那么函数调用栈中的数据（栈帧）会越来越多，而函数调用栈空间一般不大，堆栈空间不足以存储所有的调用信息，从而导致堆栈溢出。...讨论尾递归避免堆栈溢出什么是尾递归？「尾递归是指一个递归函数的最后一个操作是递归调用自身，并且该调用的返回值直接返回给函数的调用者，而不进行任何其他的计算或处理。这种形式的递归称为尾递归」。...所以对于尾递归代码，不需要想栈里压入数据，也就不存在堆栈溢出的问题。...但是在实际开发过程中，尾递归其实并没有太大作用，不能期望它来规避递归导致的堆栈溢出问题，主要表现在：并不是所有编程语言都支持尾递归优化并不是所有的递归都可以改成尾递归能改成尾递归的代码也就都可以改成迭代方式

1791 0

C语言函数：编程世界的魔法钥匙（2）-学习笔记

if (n == 0 || n == 1)限制条件 为什么说终止条件是必不可少的呢？你可以想象一下，一辆火车如果没有刹车，那会是什么情况，是不是停不下来？...终止条件就像是一个“刹车”，如果没有它，函数会不停地调用自身，导致无限循环，最终程序可能会因为栈溢出等错误而崩溃。因此，终止条件可以有效的防止代码的无限循环。...当没有限制条件后，这个函数就会自己调自己，一直循环，发生死递归，出现堆栈溢出。 1.3 什么叫堆栈溢出呢？内存划分为栈区、堆区、静态区。...这就是为什么我们需要终止条件的原因。以下是一些避免栈溢出错误的常见方法： 1. 优化函数调用：减少函数的嵌套调用层数，避免不必要的深层递归。对于可以使用迭代解决的问题，优先选择迭代而不是递归。...2.内存使用更高效递归可能导致大量的栈空间使用，容易出现栈溢出错误。迭代一般在固定的内存区域操作，对内存的使用更可控。 3.更易理解和调试对于一些复杂的递归逻辑，理解和跟踪其执行过程可能较为困难。

531 0

攻击本地主机漏洞（中）

如果输入值大于其长度，它将覆盖金丝雀值，导致程序抛出分段错误（segfault），因为输入值的内容试图覆盖内存的受限区域。过去，Linux允许在堆栈上执行指令。...子例程是较大程序的一部分，包括一组执行任务的指令。可以使用库函数，而不是将恶意负载写入堆栈，恶意程序可以使用其条目位置覆盖返回地址。...为支持此练习而开发的文件和源代码与本书附带的在线内容一起提供（有关详细信息，请参阅附录）。为了完成此练习，我们需要禁用一些内置保护机制，例如堆栈金丝雀和可执行空间保护。...为了插入恶意负载并执行shell，而不是一堆a，我们需要知道在500字节的负载中，它在哪里覆盖RBP以导致跳转。...Metasploit有两个工具可以促进此活动，msf-pattern_create（或pattern_create），它创建一个唯一的模式作为不包含任何重复序列的输入缓冲区（而不是a）发送，以及msf-pattern_offset

1.4K2 0

递归的递归之书：引言到第四章

相比之下，函数递归调用自身的情况被称为递归情况。所有递归函数都需要至少一个基本情况和至少一个递归情况。如果没有基本情况，函数永远不会停止进行递归调用，最终导致堆栈溢出。...它并不是如此深度递归，以至于可能导致堆栈溢出。树具有自相似结构：分叉点看起来类似于较小子树的根。递归通常涉及自相似性和可以分解为更小、相似子问题的问题。...如果您的树结构具有如此多层的分支，以至于递归函数在到达叶子之前就会导致堆栈溢出，那么递归就不是一个合适的解决方案。另一方面，递归是创建编程语言编译器的最佳方法。...即使性能不是问题，递归sum()函数如果传递一个要求求和的数目为数万的列表会导致堆栈溢出。递归是一种高级技术，但并不总是最佳方法。...请记住，特别深的树数据结构会导致堆栈溢出，因为算法遍历更深的节点。这是因为每个更深入树的层级都需要另一个函数调用，太多的函数调用而没有返回会导致堆栈溢出。然而，广泛、平衡良好的树不太可能会那么深。

6381 0

MIT 6.858 计算机系统安全讲义 2014 秋季（一）

，因为堆溢出会立即导致崩溃，而不是悄无声息地破坏堆并在未来某个不确定的时间导致失败。...基本上，我们创建了一种新类型的机器，它由堆栈指针驱动，而不是常规指令指针！随着堆栈指针沿着堆栈移动，它执行的小工具的代码来自预先存在的程序代码，数据来自缓冲区溢出创建的堆栈数据。...允许递归调用chroot()以从 chroot 监狱中逃脱，因此 chroot 对于以 root 身份运行的进程来说不是一种有效的安全机制。...解决方案：二进制文件由 root 所有，服务是组所有者，模式 0410。 为什么是 0410（用户读取，组执行），而不是 0510（用户读取和执行）？ 为什么不按用户处理？...（坏主意，但让我们弄清楚为什么…）大量潜在的缓冲区溢出可能导致 root 访问权限。需要在 gcc 可能打开文件的每个地方进行检测。

1661 0

finished with exit code -1073740791 (0xC0000409)

错误原因这个错误码(-1073740791)的具体含义是"异常栈溢出"，即在程序执行过程中，堆栈空间不足以容纳额外的调用栈导致溢出。...一旦达到操作系统分配给进程堆栈的最大空间限制，就会导致堆栈溢出，进而引发这个错误。解决方案1. 优化递归函数如果程序中存在递归函数并且递归深度过大，可以优化递归函数以减少堆栈空间的使用。...可以通过检查程序的逻辑、变量的生命周期以及资源的释放等方面，找出可能导致堆栈溢出的问题，并进行修复。4. 借助工具定位问题可以借助调试工具和性能分析工具来定位堆栈溢出的问题。...总结"finished with exit code -1073740791 (0xC0000409)"错误是一种堆栈溢出的错误，意味着程序的调用栈空间不足以容纳额外的调用栈导致溢出。...但是，当计算第 10000 个数时，普通递归方式会导致堆栈溢出错误，而优化后的尾递归方式可以正常计算出结果。这个示例代码展示了如何通过优化递归函数来避免堆栈溢出错误，并提升程序的性能和可靠性。

8564 0

算法刷题小技巧总结

（小背包——背包最大体积2000000，最多装载16个物品，每个物品体积2400）判断组合数的奇偶性，二进制n&m==m为奇数，反之为偶数。...; 注意字符串和字符数组的区别：字符串最后会有一个’\0’ 斐波那契数列通常用递归来求，如果不用递归式的定义，斐波那契数列的通项公式为： ?...（16）条件替换replace_if （17）n次填充fill_n （18）随机生成n个元素generate （19）操作容器中的每一个元素for_each （20）条件移除remove_if 并不是所有迭代器都有加减法...堆栈溢出的几个问题（1）vector如果要随机访问进行赋值，则必须先分配空间；（2）局部数组不能太太，否则会产生堆栈溢出；可以使用全局数组或者动态分配。...（3）可以使用long long int防止数据太小导致的问题；

4750 0

iOS 内存概述

，即DATA区全局变量是指变量值可以在运行时被动态修改，而静态变量是static修饰的变量，包含静态局部变量和静态全局变量常量区（.rodata）编译时期分配的内存空间，程序结束后系统自动释放...只读区域主要存放：已经使用且没有指向的字符串常量字符串常量因为可能在程序中多次使用，所有在程序运行前提前分配内存代码区（.text）编译时分配只读区域主要存放：程序运行的代码，代码会编译成二进制存到内存...函数栈（栈帧）函数在运行中且未完成时期占用的一块独立的连续内存区域每一个线程都有专用的栈空间，该栈空间可以在线程期间自由使用，当前线程的函数共享改栈空间，每一个函数使用的栈空间是一个栈帧，所有的栈帧组成了这个线程完整的栈...函数的调用是发生在栈上，每一个函数的相关信息（局部变量，调用记录等）都存储在一个栈帧中，每执行一次函数调用就会生成一个新的栈帧，然后将其压入函数栈，当函数执行结束时，则将函数对应的栈帧出栈并释放堆栈溢出...一般情况下我们是不需要考虑堆栈的大小问题，但是堆栈不是无上限的，过多的递归会导致栈溢出，过多的alloc会导致堆溢出预付堆栈溢出的方法：避免层次过深得递归调用不要使用过多的局部变量，控制局部变量大小

4750 0

iOS内存详解

中一般以0x1开头可读可写区域主要用来存放：未初始化的全局变量和静态变量，即BSS区已初始化的全局变量和静态变量，即DATA区全局变量是指变量值可以在运行时被动态修改，而静态变量是static...，所有在程序运行前提前分配内存代码区（.text）编译时分配只读区域主要存放：程序运行的代码，代码会编译成二进制存到内存函数栈（栈帧）函数在运行中且未完成时期占用的一块独立的连续内存区域每一个线程都有专用的栈空间...，该栈空间可以在线程期间自由使用，当前线程的函数共享改栈空间，每一个函数使用的栈空间是一个栈帧，所有的栈帧组成了这个线程完整的栈函数的调用是发生在栈上，每一个函数的相关信息（局部变量，调用记录等）都存储在一个栈帧中...，每执行一次函数调用就会生成一个新的栈帧，然后将其压入函数栈，当函数执行结束时，则将函数对应的栈帧出栈并释放堆栈溢出一般情况下我们是不需要考虑堆栈的大小问题，但是堆栈不是无上限的，过多的递归会导致栈溢出...，过多的alloc会导致堆溢出预付堆栈溢出的方法：避免层次过深得递归调用不要使用过多的局部变量，控制局部变量大小避免占用大内存的对象的分配，及时释放在适当情况下调用系统API修改线程的堆栈大小

6562 0

JavaScript 中的尾调用和优化

而下面这个栗子就不是尾调用： function f(x) { return 1 + g(x)} 原因是它的最后一步操作是将 g 函数调用的返回值和 1 进行加法操作，而不是调用其他函数，所以它不是尾调用...为什么说尾调用重要呢，原因是它不会在调用栈上增加新的堆栈帧，而是直接更新调用栈，调用栈所占空间始终是常量，节省了内存，避免了爆栈的可能性。...f 函数的返回值，而不是直接返回 f 的返回值，直接返回的只有 g 函数的返回值。...undefined} 可以看到 return 语句返回的只是一个 undefined 而并非 bar 函数的返回值，所以这里不存在尾调用。...堆栈信息丢失除了开发者难以辨别尾调用以外，另一个原因则是堆栈信息会在优化的过程中丢失，这对于调试是不方便的，另外一些依赖于堆栈错误信息来进行用户信息收集分析的工具可能会失效。

1.1K1 0

数据结构与算法 --- 递归（一）

，就会塞满函数栈，导致堆栈溢出。...如何避免出现堆栈溢出呢？「可以通过在代码中限制递归调用的最大深度」。...使用递归编程有利有弊，递归编程的好处是使用递归编写的代码的表达能力强，写起来简洁，而递归编程的劣势是空间复杂度高，且存在堆栈溢出和重复计算的问题，因此，在实际开发过程中，可以根据实际情况来决定是是否使用递归实现...虽然理论上可以将所有递归算法改写为迭代循环的非递归写法，但实际上有些算法可能更适合使用递归实现，而另一些算法则更适合使用迭代循环实现。...例如，递归算法通常在树形结构的遍历和图形搜索等算法中使用，而迭代循环则更适合处理数值计算等需要大量循环迭代的算法。

2732 0

数据结构与算法 --- 递归（一）

3482 0

一次通过dump文件分析OutOfMemoryError异常代码定位过程

这可能会导致应用程序无法继续正常运行。内存泄漏：OutOfMemoryError 有时会暗示存在内存泄漏问题。即使没有明显的内存泄漏，也可能是应用程序中某些对象持续增加，导致堆空间耗尽。...什么是OutOfMemoryError异常在 Java 中，OutOfMemoryError 是一种错误（Error），而不是异常（Exception）。...OutOfMemoryError 可能由以下几种情况引起：堆内存溢出（Heap Space）：当 Java 程序中创建了太多的对象，而堆内存无法满足这些对象的需求时，就会发生堆内存溢出。...当递归调用层级过深或者方法调用过多时，栈空间可能会溢出，导致栈溢出错误。...如果程序中频繁申请直接内存而没有及时释放，可能会导致直接内存溢出。

2421 0

尾递归的后续探究

3.1 隐式优化问题首先，由于引擎消除尾递归是隐式的，函数是否符合尾调用而被消除了尾递归很难被程序员自己辨别。...为了写出正确的尾递归方法，你需要首先了解是不是正确的尾调用形式。同时你可能还需要尝试写不同的尾递归和普通递归的写法，调整递归参数让能超过调用栈，并不断的进行调试。...而且你也不能保证调试出来的结果是不是因为运气好而表现出了正常的结果。这也就是隐式优化所带来的一大问题。...3.2 调用栈丢失问题其次，尾调用优化要求除掉尾调用执行时的调用堆栈，这将导致执行流中的堆栈信息丢失。这也就导致依赖调用堆栈信息的调试和错误收集过程受到了影响。...同样的STC对比PTC也有两个缺点：渐进增强：一些值的计算需要在不断的递归中得到逼近的值，PTC的写法可以帮助得到一个爆栈前的值；维护难度：新的语法意味着需要维护两套后端； 5 总结 Chrome

1K10 0

尾递归的后续探究

1.5K2 2

JavaScript是如何工作的?

JavaScript 引擎将逐行解析代码并将该代码转换为机器代码（二进制/位格式）。现在，浏览器可以理解该机器代码并相应地运行。这是一些 JS 引擎示例 ?...在这里，我们面临一个主要的内存泄漏问题。那么什么是内存泄漏？内存堆的空间有限。如果我们继续使用堆空间而不关心释放未使用的内存。当堆中没有更多可用内存时，这将导致内存泄漏问题。...执行上下文栈堆栈是遵循后进先出（LIFO）原理的数据结构（进入堆栈的最后一项将是要从堆栈中删除的第一项）。 ECS 存储所有功能的执行上下文。执行上下文定义为存储局部变量，函数和对象的对象。...这就是使 JavaScript 单线程的原因。您一定听说过堆栈溢出。这意味着什么？-ECS 的空间也有限。因此，如果我们继续在堆栈顶部添加功能。在某个时候，将没有更多的空间来添加更多的堆栈框架。...好吧，这进入了无限递归，并且我们有一个堆栈溢出错误。 ? 因此，正如我所提到的，JavaScript 是一种简单的线程语言，这意味着它只有一个调用堆栈任务，因此一次只能执行一个语句。

2.8K3 1

解析Exception和C#处理Exception的常用方法总结

System.StackOverflowException 挂起的方法调用过多而导致执行堆栈溢出时引发的异常。 ...System.OverflowException 在选中的上下文中所进行的算数运算、类型转换或转换操作导致溢出时引发的异常。 ...System.IO.FileNotFoundException 试图访问磁盘上不存在的文件失败时引发的异常。.../// 提取的例外 /// 最后提取的堆栈跟踪（对于递归）， String.Empty...or null /// 提取的堆栈数（对于递归） /// Syste.String

2.2K10 0

Python 之父的解析器系列之五：左递归 PEG 语法

我曾几次提及左递归是一块绊脚石，是时候去解决它了。基本的问题在于：使用递归下降解析器时，左递归会因堆栈溢出而导致程序终止。【这是我的 PEG 系列的第 5 部分。...if term(): return True return False 也就是expr() 以调用expr() 开始，后者也以调用expr() 开始，以此类推……这只能以堆栈溢出而结束...但是这仍然存在一些问题：因为像'+' 和'-' 这样的运算符，基本上是二进制的（在 Python 中），当我们解析像a + b + c 这样的东西时，我们必须遍历解析的结果（基本上是列表['a'，'+'...决定性的洞察（这是我自己的，虽然我可能不是第一个想到的）是我们可以使用记忆缓存而不是全局变量，将一次调用的结果保存到下一次，然后我们不需要额外的oracle_expr() 函数——我们可以生成对 expr...至于下周，我打算论述在语法中添加“动作”（actions），这样我们就可以为一个给定的备选项的解析方法，自定义它返回的结果（而不是总要返回一个 Node 实例）。

8273 0

漏洞分析入门一

最容易想到的就是通过扫描PE文件的倒入表，查找是否存在危险函数，这种扫描方法速度快，而且比较有效，但是也有缺点：检出率不高，存在遗漏，因为只能扫描到倒入表这一方面，而如果一些模块是使用了静态lib链接的话...所以还需要加以指令分析的方法，但是指令分析的实现难度和成本都比较高，因为要考虑到所有的漏洞模式，这也导致了另一个缺点检测速度非常慢。 3....在物理机中是没有堆栈的概念，只是一片空间而也，只有当操作系统与程序运行起来后才给与了堆栈的概念。 2. 栈（操作系统）：由编译器自动分配释放，存放函数的参数值，局部变量的值等。...没有对密钥进行长度检测，导致堆栈溢出。...0x06:总结实战部分只讲了一些简单漏洞分析，二进制漏洞所带来的危害巨大，但是发现起来也相对困难，随着攻防对抗的增加，各种各样的防护手段和攻击技巧也层出不穷。

1.2K2 1

理论：第十三章：堆溢出，栈溢出的出现场景以及解决方案

堆溢出的情况及解决方案 OutofMemoryError：Java heap space 堆内存中的空间不足以存放新创建的对象 ?...解决方案：-XX:MaxMetaspaceSize=512m 设计一个堆溢出的程序：https://blog.csdn.net/java_wxid/article/details/103021907 栈溢出几种情况及解决方案...当函数内部的数组过大时，有可能导致堆栈溢出。递归调用层次太多。递归函数在运行时会执行压栈操作，当压栈次数太多时，也会导致堆栈溢出。指针或数组越界。...这种情况最常见，例如进行字符串拷贝，或处理用户输入等等。...解决这类问题的办法有两个增大栈空间改用动态分配，使用堆（heap）而不是栈（stack）直接查询生产环境服务器内存占用情况，通过命令定位到具体的那行代码

2K1 0

点击加载更多

扫码

添加站长进交流群

领取专属 10元无门槛券

手把手带您无忧上云

为什么递归的二进制搜索有时会导致一些而不是所有不存在的输入的堆栈溢出？

相关·内容

数据结构与算法 --- 递归（二）

C语言函数：编程世界的魔法钥匙（2）-学习笔记

攻击本地主机漏洞（中）

递归的递归之书：引言到第四章

MIT 6.858 计算机系统安全讲义 2014 秋季（一）

finished with exit code -1073740791 (0xC0000409)

算法刷题小技巧总结

iOS 内存概述

iOS内存详解

JavaScript 中的尾调用和优化

数据结构与算法 --- 递归（一）

数据结构与算法 --- 递归（一）

一次通过dump文件分析OutOfMemoryError异常代码定位过程

尾递归的后续探究

尾递归的后续探究

JavaScript是如何工作的?

解析Exception和C#处理Exception的常用方法总结

Python 之父的解析器系列之五：左递归 PEG 语法

漏洞分析入门一

理论：第十三章：堆溢出，栈溢出的出现场景以及解决方案

扫码

相关资讯

热门标签

活动推荐

运营活动

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐