Excel VBA的查找与二进制搜索有多好/多快？我的平台是Office 11 | 2003,我将在三张值上搜索A列的字符串.行总数~14万
如果值得我参考哪个库和函数进行排序然后进行二分查找？据报道,二进制搜索字符串/文本存在潜在问题.
......必须注意一件事.使用带有sortedtext的二进制搜索公式需要谨慎. Aladin A.,Excel MVP
Excel查找:
Worksheets(1).Range("A:A").Find("PN-String-K9", LookIn:=xlValues, LookAt:=xlWhole)
我正在寻找数学证明,而不仅仅是答案.
我正在阅读有关在排序的字符串数组中搜索(范围)字符串的内容.
它说:
如果要查找以"h"开头的所有字符串,可以对字符串"h"和"h\uFFFF"运行二进制搜索.这给出了以"h"开头的所有键的频带的所有索引.请注意,二进制搜索可以返回索引所在的索引,即使它实际上不在数组中也是如此.
我对这一段不明白.
h\uFFFF它是如何帮助/用于二进制搜索的,并且最后的句子也意味着即使这个搜索也有问题？
有什么帮助可以理解这里的内容吗？
我需要使用Arrays.binarySearch方法查找排序数组中的所有元素。我想在lowerbound = pos + 1（pos是前一个匹配项）中迭代二进制搜索，但binarySearch不能保证返回第一个匹配项（最小匹配索引）？
我怎样才能做到这一点？
我需要在排序范围内插入一个元素,但我还需要知道它的索引(范围内的元素数量少于元素).我想在O(logN)时间内完成此操作.我可以使用基本的C++容器吗？
我想使用std :: multimap,使用这个容器,我可以将元素插入到具有O(logN)复杂性的位置.但是要获取索引,我需要调用std :: distance,它需要进行O(N)操作,因为multimap迭代器不是随机访问.
另一种方法是使用排序的std :: vector和std :: binary_search算法.在这种情况下,搜索采用O(logN),但插入将采用O(N)操作,因为向量中间的插入是线性操作.
那么,是否有std/boost容器可用于达到结果,或者我需要为此实现自己的结构？谢谢!
我知道二分搜索是如何工作的，但当我需要实现二分搜索时，我总是会犯一些小错误。
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int low = 1, high = nums.size() - 1;
while (low < high) {
int mid = low + (high - low) * 0.5;
int cnt = 0;
for (auto a : nums) {
if (a <= mid) ++cnt;
}
if (cnt <= mid) low = mid + 1;
else high = mid;
}
return low;
}
};
有几个地方让我很困惑：
1. while循环的条件low<high or low<=high
2. a<=mid or a<mid …
我想查找排序数组中是否存在数字。一个数组包含从 1 到 63 的斐波那契数。下面是斐波那契数生成器和它的一些输出。
stacksize = 10000 # default 128 stack
from functools import lru_cache
@lru_cache(stacksize)
def nthfibonacci(n):
if n <= 1:
return 1
elif n == 2:
return 1
elif n > 2:
return nthfibonacci(n - 2) + nthfibonacci(n - 1)
output = [nthfibonacci(k) for k in range(1,63+1)]
# truncated output: [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610,987,
1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368,.....]
现在我想找到数字 7 是否 …
尝试了解 Codility NailingPlanks 的解决方案。
\n\n问题链接：\n https://app.codility.com/programmers/lessons/14-binary_search_algorithm/nailing_planks/
\n\n\n\n\n给定两个由 N 个整数组成的非空数组 A 和 B。\n 这些数组代表 N 个木板。更准确地说，A[K] 是第 K\xe2\x88\x92 个木板的起点，\n B[K] 是终点。
\n\n接下来，给出一个由 M 个整数组成的非空数组 C。该数组代表 M 个钉子。更准确地说，C[I] 是您可以敲入第 I\xe2\x88\x92 个钉子的位置。
\n\n如果存在钉子 C[I]\n 使得 A[K] \xe2\x89\xa4 C[I] \xe2\x89\ ，我们说木板 (A[K], B[K]) 被钉住xa4 B[K]。
\n\n目标是找到必须使用的最少钉子数量，直到钉完所有木板。换句话说，您应该找到一个值 J，使得仅使用前 J 个钉子后即可钉好所有木板。更准确地说，对于每个木板 (A[K], B[K]) 使得 0 \xe2\x89\xa4 K\n < N，应该存在一个钉子 C[I] 使得 I < J 且 A[K ] \xe2\x89\xa4 C[I] \xe2\x89\xa4\n B[K]。
\n
解决方案链接：\n https://github.com/ZRonchy/Codility/blob/master/Lesson12/NailingPlanks.java
\n\nimport java.util.Arrays;\n\nclass Solution {\n …许多常见的操作都没有内置到 Raku 中，因为它们可以用（元）运算符和/或函数的组合来简洁地表达。这感觉就像折半查找有序数组的应该是那样的可表达的（也许用.rotor？或者…？），但我还没有找到一个特别好的办法这样做。
例如，我想出的用于搜索已排序的 Pairs 数组的最佳方法是：
sub binary-search(@a, $target) {
when +@a ? 1 { @a[0].key == $target ?? @a[0] !! Empty }
&?BLOCK(@a[0..^*/2, */2..*][@a[*/2].key ? $target], $target)
}
这并不可怕，但我无法动摇它可能会好得多的感觉（在简洁性和可读性方面）。谁能看到我可能缺少什么优雅的操作组合？
假设整数的排序列表如下：
data = [1] * 3 + [4] * 5 + [5] * 2 + [9] * 3
# [1, 1, 1, 4, 4, 4, 4, 4, 5, 5, 9, 9, 9]
我想找到值发生变化的索引，即
[3, 8, 10, 13]
一种方法是使用itertools.groupby：
cursor = 0
result = []
for key, group in groupby(data):
cursor += sum(1 for _ in group)
result.append(cursor)
print(result)
输出
[3, 8, 10, 13]
这种方法的复杂度是 O(n)。另一种可能的方法是使用bisect.bisect_left：
cursor = 0
result = []
while cursor < len(data):
cursor …