问题标签 [bisection]

是否有一个库函数对列表/元组执行二进制搜索，如果找到则返回项目的位置，如果没有则返回“假”（-1、无等）？

我在bisect 模块中找到了 bisect_left/right 函数，但即使项目不在列表中，它们仍然返回一个位置。这对于他们的预期用途来说非常好，但我只想知道一个项目是否在列表中（不想插入任何东西）。

我想过使用bisect_left然后检查该位置的项目是否等于我正在搜索的项目，但这似乎很麻烦（而且我还需要检查该数字是否可以大于我列表中的最大数字）。如果有更好的方法我想知道。

编辑澄清我需要这个：我知道字典非常适​​合这个，但我试图保持内存消耗尽可能低。我的预期用途是一种双向查找表。我在表中有一个值列表，我需要能够根据它们的索引访问这些值。如果该值不在列表中，我还希望能够找到特定值的索引或 None 。

为此使用字典将是最快的方法，但会（大约）使内存需求增加一倍。

我在问这个问题时认为我可能忽略了 Python 库中的某些内容。正如 Moe 建议的那样，我似乎必须编写自己的代码。

我需要模拟Fluxbox窗口管理器的窗口放置策略。

作为粗略的指导，一次将一个随机大小的窗口可视化填充屏幕，每个窗口的粗略大小导致屏幕上平均有 80 个窗口，而没有任何窗口重叠。

如果您的系统上安装了 Fluxbox 和 Xterm，您可以尝试使用xwinmidiarptoy BASH 脚本来查看我想要发生的事情的粗略原型。请参阅我写的关于它的xwinmidiarptoy.txt注释，解释它的作用以及应该如何使用它。

重要的是要注意窗口将关闭，并且之前关闭的窗口占用的空间再次可用于放置新窗口。

该算法需要是一种在线算法，“以串行方式逐个处理数据，即按照将输入馈送到算法的顺序，而无需从一开始就提供整个输入。”

Fluxbox 窗口放置策略有三个我想模拟的二进制选项：

• Windows 构建水平行或垂直列（可能）

• 窗户从左到右或从右到左放置

• 窗户从上到下或从下到上放置

目标算法和窗口放置算法之间的差异

坐标单位不是像素。将放置块的网格将是 128 x 128 单位。此外，放置区域可以被放置在网格内的边界区域进一步缩小。

为什么算法有问题？

它需要在音频应用程序中的实时线程的最后期限内运行。

目前我只关心获得一个快速的算法，不要担心实时线程的影响以及由此带来的所有编程障碍。

尽管该算法永远不会放置与另一个重叠的窗口，但用户将能够放置和移动某些类型的块，重叠窗口将存在。用于存储窗口和/或空闲空间的数据结构需要能够处理这种重叠。

到目前为止，我有两个选择，我为它们构建了松散的原型：

1) 将 Fluxbox 放置算法移植到我的代码中。

问题是，当我尝试使用算法放置 256 个块的最坏情况时，客户端（我的程序）被踢出音频服务器（JACK ）。该算法在放置第 256 个窗口时对已放置的块列表执行超过 14000 次完整（线性）扫描。

为了演示这一点，我创建了一个名为text_boxer-0.0.2.tar.bz2的程序，它将文本文件作为输入并将其排列在 ASCII 框中。发布make构建它。有点不友好，使用--help（或任何其他无效选项）作为命令行选项列表。您必须使用该选项指定文本文件。

2）我的替代方法。

仅部分实现，该方法对每个矩形空闲未使用空间区域使用数据结构（窗口列表可以完全分开，并且不需要测试该算法）。该数据结构充当双向链表中的节点（具有排序插入），并包含左上角的坐标以及宽度和高度。

此外，每个块数据结构还包含四个链接，这些链接连接到四个边中每一个上的每个紧邻（接触）块。

重要规则：每个积木每边只能接触一个积木。这是特定于算法存储空闲未使用空间的方式的规则，并且与实际窗口可能相互接触的数量无关。

这种方法的问题是，它非常复杂。我已经实现了简单的案例，其中 1) 从块的一个角移除空间，2) 拆分相邻块以便遵守重要规则。

不太直接的情况，即要删除的空间只能在一列或一行框中找到，仅部分实现 - 如果要删除的块之一与宽度（即列）或高度（即行）然后出现问题。更不用说这个事实，它只检查一框宽的列，一框高的行。

我已经在 C 中实现了这个算法——我在这个项目中使用的语言（我已经有几年没有使用 C++ 并且在将所有注意力都集中在 C 开发之后使用它感到不舒服，这是一种爱好）。实现是 700 多行代码（包括大量的空白行、大括号行、注释等）。该实现仅适用于水平行+左右+上下放置策略。

所以我要么必须添加一些方法，使这+700 行代码适用于其他7 个放置策略选项，要么我将不得不为其他7 个选项复制那些+700 行代码。这些都没有吸引力，第一，因为现有代码足够复杂，第二，因为臃肿。

由于缺少功能，该算法甚至还没有处于我可以在实时最坏情况下使用它的阶段，所以我仍然不知道它实际上是否比第一种方法表现更好或更差。

该算法的 C 实现的当前状态是freespace.c。我gcc -O0 -ggdb freespace.c用来构建并在 xterm 中运行它，大小至少为 124 x 60 字符。

那里还有什么？

我浏览并打折：

• Bin Packing算法：它们对最优拟合的强调不符合该算法的要求。

• 递归二等分放置算法：听起来很有希望，但这些是用于电路设计的。他们的重点是最佳电线长度。

这两者，尤其是后者，所有要放置/包装的元素在算法开始之前都是已知的。

您对此有何看法？你会如何处理它？我应该看哪些其他算法？或者我应该研究什么概念，因为我没有学过计算机科学/软件工程？

如果需要更多信息，请在评论中提问。

自从提出这个问题后，进一步的想法得到了发展

• 我的“替代算法”与空间哈希图的某种组合，用于识别要放置的大窗口是否会覆盖几个空闲空间块。

我需要一种算法来执行二维二等分法来解决 2x2 非线性问题。示例：两个方程f(x,y)=0，g(x,y)=0我想同时求解。我非常熟悉一维二分法（以及其他数值方法）。假设我已经知道解决方案位于界限x1 < x < x2和y1 < y < y2.

在网格中，起始边界是：

我知道这些值f(A), f(B), f(C) and f(D)以及g(A), g(B), g(C) and g(D). 要开始二分，我想我们需要将点沿边缘和中间分开。

现在考虑组合的可能性，例如检查是否f(G)*f(M)<0 AND g(G)*g(M)<0似乎势不可挡。也许我让这有点太复杂了，但我认为应该有一个多维版本的二分法，就像牛顿拉夫森可以很容易地使用梯度算子进行多面化一样。

欢迎任何线索、评论或链接。

为什么在二分法中最好计算 a 和 b 之间的中点 c

而不是更简单的：

所有变量都是浮点数。

有没有我可以在网上找到的二等分方法，专门用于 python？

例如，给定这些方程，我如何使用二分法求解它们？

我不知道该怎么做，我知道我必须循环精确定位中点等

然后主要我有这个

在 Python 中，如何找到排序列表中第一个大于阈值的值的索引？

我可以想到几种方法（线性搜索，手写二分法，..），但我正在寻找一种干净且合理有效的方法。由于这可能是一个很常见的问题，我相信有经验的 SOers 可以提供帮助！

谢谢！

我以前遇到过这个问题，但现在它以某种方式工作。

现在我有以下问题。在使用相同的函数调用 boost::bisect 之前，我需要将值绑定到成员函数中。我找到了很好的教程，并且我已经按照它进行操作，但似乎我仍然做错了什么。

起初，我创建了测试类，并在其中进行了以下工作：

之后，我“即时添加绑定，因为我认为它可以工作”

结果是一个错误。错误：在抛出 'boost::exception_detail::clone_impl >' 的实例后调用终止 what()：函数 boost::math::tools::bisect 中的错误：boost::math::tools 中的符号没有变化： :bisect，要么找不到根，要么区间中有多个根（f(min) = -0.0032916729090909091）。

无论如何，这里的 class::function 由于某种原因不能作为具有绑定的成员函数工作。我以非会员身份对其进行了测试，并且可以正常工作

考虑二分算法来求平方根。每一步都取决于前一步，所以在我看来，并行化它是不可能的。我错了吗？

还要考虑类似的算法，如二分搜索。

编辑

我的问题不是二分法，而是非常相似。我有一个单调函数f(mu)，我需要找到 mu where f(mu)<alpha。一个核心需要 2 分钟来计算f(mu)，我需要非常高的精度。我们有一个大约 100 个核心的农场。我的第一次尝试是仅使用 1 个核心，然后f使用动态步骤扫描 的所有值，具体取决于我与alpha. 现在我想使用整个农场，但我唯一的想法是f在等间距点计算 100 的值。

如果我使用二分法找到多项式的根，并且在某些情况下取决于多项式，根可能是负数，也可能是正数。

我知道我可以根据评估多项式的​​结果来确定根是负数还是正数……但是我不确定我将使用什么作为 x。

任何人都可以在这里提供任何见解吗？