标签: binary-search

有没有在使用二进制搜索,像函数lower_bound,但返回的最后一个项目低于或相等,以根据给定的断言？

lower_bound 定义为:

查找具有大于或等于指定值的有序范围中的第一个元素的位置,其中排序标准可以由二元谓词指定.

并且upper_bound:

查找具有大于指定值的有序范围中第一个元素的位置,其中排序条件可以由二元谓词指定.

具体来说,我有一个时间排序事件的容器,在给定的时间内,我想找到之前或之前的最后一个项目.我可以通过上/下限,反向迭代器和使用std::greater或std::greater_equal？的某种组合来实现这一点.

编辑:如果你在数组开始之前要求一个点,则需要对user763305的建议进行调整:

iterator it=upper_bound(begin(), end(), val, LessThanFunction());
if (it!=begin()) {
  it--; // not at end of array so rewind to previous item
} else {
  it=end(); // no items before this point, so return end()
}
return it;

简单的问题 - 给定一个IList<T>如何在不自己编写方法的情况下执行二进制搜索,而不将数据复制到具有内置二进制搜索支持的类型.我目前的状况如下.

• List<T>.BinarySearch() 不是会员 IList<T>
• 没有相应的ArrayList.Adapter()方法List<T>
• IList<T>不继承IList,因此使用ArrayList.Adapter()是不可能的

我倾向于认为使用内置方法是不可能的,但我无法相信BCL/FCL中缺少这样的基本方法.

如果不可能,谁可以提供最短,最快,最智能或最美丽的二进制搜索实现IList<T>？

UPDATE

我们都知道在使用二进制搜索之前必须对列表进行排序,因此您可以假设它是.但我认为(但没有验证)排序是同样的问题 - 你如何排序IList<T>？

结论

似乎没有内置二进制搜索IList<T>.可以使用First()和OrderBy()LINQ方法进行搜索和排序,但它可能会受到性能影响.自己实现它(作为扩展方法)似乎是你能做到的最好的.

从熊猫文档中,我收集到了独特值的索引使得某些操作有效,并且偶尔会容忍非唯一索引.

从外部来看,看起来不是非独特的指数以任何方式被利用.例如,以下ix查询足够慢,似乎正在扫描整个数据帧

In [23]: import numpy as np
In [24]: import pandas as pd
In [25]: x = np.random.randint(0, 10**7, 10**7)
In [26]: df1 = pd.DataFrame({'x':x})
In [27]: df2 = df1.set_index('x', drop=False)
In [28]: %timeit df2.ix[0]
1 loops, best of 3: 402 ms per loop
In [29]: %timeit df1.ix[0]
10000 loops, best of 3: 123 us per loop

(我意识到这两个ix查询不会返回相同的东西 - 它只是一个调用ix非唯一索引的示例显得慢得多)

有没有办法哄骗熊猫使用更快的查找方法,如二元搜索非唯一和/或排序索引？

最近我在链表上遇到了一个有趣的问题.给出了单独排序的列表,我们必须从该列表中搜索一个元素.

时间复杂度不应超过O(log n).这似乎我们需要在此链表上应用二进制搜索.怎么样？由于链接列表不提供随机访问,如果我们尝试应用二进制搜索算法,它将达到O(n),因为我们需要找到列表的长度并转到中间.

有任何想法吗？

我正在尝试在JavaScript中实现二进制搜索算法.事情似乎没问题,但我的回复陈述似乎是未定义的回归？谁能说出这里有什么问题？

小提琴:http://jsfiddle.net/2mBdL/

谢谢.

var a = [
    1,
    2,
    4,
    6,
    1,
    100,
    0,
    10000,
    3
];

a.sort(function (a, b) {
    return a - b;
});

console.log('a,', a);

function binarySearch(arr, i) {
    var mid = Math.floor(arr.length / 2);
    console.log(arr[mid], i);

    if (arr[mid] === i) {
        console.log('match', arr[mid], i);
        return arr[mid];
    } else if (arr[mid] < i && arr.length > 1) {
        console.log('mid lower', arr[mid], i);
        binarySearch(arr.splice(mid, Number.MAX_VALUE), i);
    } else if (arr[mid] > i && arr.length > …

我想得到我正在测试的元素的迭代器binary-search.但它只返回一个bool指示是否找到该值的指示.如何获得迭代器？

我正在阅读一本算法书,其中包含以下二进制搜索算法:

public class BinSearch {
  static int search ( int [ ] A, int K ) {
    int l = 0 ;
    int u = A. length ?1;
    int m;
    while (l <= u ) {
      m = (l+u) /2;
      if (A[m] < K) {
        l = m + 1 ;
      } else if (A[m] == K) {
        return m;
        } else {
          u = m?1;
        }
       }
       return ?1;
      }
 }

作者说:"错误在于m = (l+u)/2;它可能导致溢出的分配,应该被替换为m = l …

我正在努力将Perl程序移植到Java,并且随时学习Java.原始程序的核心组件是Perl模块,它使用二进制搜索在+500 GB排序文本文件中执行字符串前缀查找(实质上,"搜索"到文件中间的字节偏移,回溯到最近的换行,比较带有搜索字符串的行前缀,"seek"到那个字节偏移的一半/两倍,重复直到找到...)

我已经尝试了几种数据库解决方案,但发现没有什么比这个大小的数据集纯粹的查找速度更好.您知道任何实现此类功能的现有Java库吗？如果做不到这一点,你能指出一些在文本文件中进行随机访问读取的惯用示例代码吗？

或者,我不熟悉新的(？)Java I/O库,但它是一个内存映射500 GB文本文件的选项(我在64位机器上,内存备用)并做二进制文件搜索内存映射的字节数组？我很想知道你必须分享的关于这个和类似问题的任何经验.

如果C++ STL包含二进制搜索树(BST)实现,或者我应该构建自己的BST对象,请知道吗？

如果STL没有实施BST,是否有可用的库？

我的目标是能够尽快找到所需的记录:我有一个记录列表(它不应该是几千个.),我在该列表中执行每帧(它的计算机游戏)搜索.我使用unsigned int作为我感兴趣的记录的标识符.无论什么方式,最快的将最适合我.

我正在寻找一个内置的Ruby方法,它具有与index二进制搜索算法相同的功能,因此需要预先排序的数组.

我知道我可以编写自己的实现,但根据" Ruby #index Method VS Binary Search ",索引使用的内置简单迭代搜索比纯Ruby版本的二进制搜索更快,因为内置方法是用C写的.

Ruby是否提供任何进行二进制搜索的内置方法？