标签: binary-search

我正在尝试优化一个在JavaScript中对字符串进行二进制搜索的函数.

二进制搜索要求您知道密钥是==枢轴还是<枢轴.

但这需要在JavaScript中进行两次字符串比较,这与C具有strcmp()返回三个值(-1, 0, +1)(小于,等于,大于)的函数的类似语言不同.

JavaScript中是否存在这样的本机函数,它可以返回三元值,以便在二进制搜索的每次迭代中只需要进行一次比较？

是否有一个库函数在列表/元组上执行二进制搜索并返回项目的位置(如果找到)和'False'(-1,None等),如果没有？

我在bisect模块中找到了函数bisect_left/right ,但即使该项不在列表中,它们仍会返回一个位置.这对于他们的预期用途来说非常好,但我只是想知道一个项目是否在列表中(不想插入任何内容).

我想过使用bisect_left然后检查那个位置的项目是否等于我正在搜索的项目,但这看起来很麻烦(我还需要检查边界是否可以大于我列表中的最大数字).如果有一个更好的方法我想知道它.

编辑为了澄清我需要这个:我知道字典非常适​​合这个,但我试图尽可能降低内存消耗.我的预期用法是一种双向查找表.我在表中有一个值列表,我需要能够根据它们的索引访问这些值.而且如果值不在列表中,我希望能够找到特定值的索引或None.

使用字典是最快的方法,但会(大约)加倍内存需求.

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

我听说有人说由于二进制搜索将搜索所需的输入减半,因此它是log(n)算法.由于我不是来自数学背景,所以我无法与之相关.有人可以更详细地解释一下吗？是否必须对对数系列做些什么？

我需要在二进制搜索树中找到第k个最小元素,而不使用任何静态/全局变量.如何有效地实现它？我在脑海中的解决方案是在O(n)中进行操作,这是最糟糕的情况,因为我计划对整个树进行顺序遍历.但在内心深处,我觉得我没有在这里使用BST属性.我的假设解决方案是正确的还是有更好的解决方案？

我需要一个与C++ STL容器兼容的二进制搜索算法,类似于std::binary_search标准库的<algorithm>头文件,但我需要它返回指向结果的迭代器,而不是一个简单的布尔值告诉我元素是否存在.

(另一方面,当他们为binary_search定义API时,标准委员会在想什么？!)

我主要担心的是我需要二进制搜索的速度,所以尽管我可以用其他算法找到数据,如下所述,我想利用我的数据被排序以获得二进制的好处这一事实搜索,而不是线性搜索.

到目前为止lower_bound,upper_bound如果缺少基准则失败:

//lousy pseudo code
vector(1,2,3,4,6,7,8,9,0) //notice no 5
iter = lower_bound_or_upper_bound(start,end,5)
iter != 5 && iter !=end //not returning end as usual, instead it'll return 4 or 6

注意:我也可以使用不属于std命名空间的算法,只要它与容器兼容即可.就像说,boost::binary_search.

这是一个家庭作业问题.他们说,这需要O(logN + logM)地方N和M是数组的长度.

让我们命名的数组a和b.显然我们可以忽略所有a[i]和b[i]i> k.
首先,让我们来比较一下a[k/2]和b[k/2].让b[k/2]> a[k/2].因此我们也可以丢弃所有b[i],其中i> k/2.

现在我们拥有所有a[i],我<k和所有b[i],其中我<k/2找到答案.

你下一步怎么做？

当给定一组静态对象(在某种意义上是静态的,一旦加载它很少会发生变化),需要重复的并发查找以及最佳性能,哪个更好,一个HashMap或一个二进制搜索使用一些自定义比较器的数组？

答案是对象或结构类型的函数吗？哈希和/或平等功能表现？哈希的独特性？清单大小？ Hashset尺寸/尺寸？

我正在看的集合的大小可以是500k到10m之间的任何地方 - 这些信息很有用.

虽然我正在寻找一个C#答案,但我认为真正的数学答案不在于语言,所以我不包括那个标签.但是,如果需要注意C#特定的事情,那么需要该信息.

在一般的二进制搜索中,我们正在寻找出现在数组中的值.但是,有时我们需要找到比目标更大或更小的第一个元素.

这是我丑陋,不完整的解决方案:

// Assume all elements are positive, i.e., greater than zero
int bs (int[] a, int t) {
  int s = 0, e = a.length;
  int firstlarge = 1 << 30;
  int firstlargeindex = -1;
  while (s < e) {
    int m = (s + e) / 2;
    if (a[m] > t) {
      // how can I know a[m] is the first larger than
      if(a[m] < firstlarge) {
        firstlarge = a[m];
        firstlargeindex = m;
      }
      e = m - …

二进制搜索比它看起来更难实现."尽管二元搜索的基本思想相对简单,但细节却令人惊讶地难以理解......" - 唐纳德克努特.

哪些错误最有可能被引入新的二进制搜索实现？

线性搜索和二进制搜索有什么区别？