标签: binary-search

如何仅使用数组实现二进制搜索？

这个早期的问题讨论了在O(n)时间内在双向链表上进行二进制搜索.该答案中的算法工作如下:

• 转到列表中间进行第一次比较.
• 如果它等于我们正在寻找的元素,我们就完成了.
• 如果它比我们正在寻找的元素更大,那么向后走一步,然后重复.
• 如果它小于我们正在寻找的元素,请向前走一半并重复.

这对于双向链接列表非常有效,因为它可以向前和向后移动,但是这种算法在单链表中不起作用.

是否有可能在单链表而不是双链表上及时进行二进制搜索O(n)？

问题:给定一个矩阵,其中每行和每列都被排序,编写一个方法来查找其中的元素.

这是一个经典的面试问题,这是我的解决方案

boolean F(int[][] matrix, int hs, int he, int ws, int we)
{
    if (hs > he || ws > we) 
        return false; 

    int m = (hs + he) / 2; 
    int n = (ws + we) / 2;

    if (matrix[m][n] == t)
    {
        return true;
    }
    else if (matrix[m][n] < t)
    {
        // find the ele in the same row, right to [m][n]
        F(m, m, n + 1, we);

        // find the ele in the same col, upper …

_{提前抱歉,如果我误用了任何条款,请随时纠正.}

我有一个排序数组dtype '<f16, |S30'.当我searchsorted在它的第一个字段上使用时,它的工作速度非常慢(对于300万个项目,大约需要0.4秒).这比bisect在元组的普通Python列表上做同样的事情要长得多.

%timeit a['f0'].searchsorted(400.)
1 loops, best of 3: 398 ms per loop

但是,如果我将float部分复制到另一个单独的数组,则搜索速度快于bisect:

b = a['f0'].copy()

%timeit b.searchsorted(400.)
1000000 loops, best of 3: 945 ns per loop

我的问题是:

1. 我做错了什么还是在NumPy中回归？
2. 有没有办法绕过这个而不重复数据？

我正在阅读有关二元搜索的内容......我知道找到中间价值的传统方式就像

mid=(hi+lo)/2

但我也看到,以避免溢出中间值是这样计算的

mid=lo+(hi-lo)/2

但为什么？？我找不到实际的原因.任何人都可以举例说明理由吗？它与其他问题不同,因为其他问题没有我想要的答案......

几天前我在一家大公司接受采访,名字不是必需的:),面试官让我找到下一个任务的解决方案:

预定义: 有未指定大小的单词字典,我们只知道字典中的所有单词都被排序(例如按字母表).我们也只有一种方法

String getWord(int index) throws IndexOutOfBoundsException

需求: 需要开发算法以使用java在字典中查找某些输入词.为此我们应该实现方法

public boolean isWordInTheDictionary(String word)

局限性: 我们无法改变字典的内部结构,我们无法访问内部结构,我们不知道字典中的元素数量.

问题: 我已经开发了修改二分法搜索,并将发布我的算法变体(工程变体),但是还有其他具有对数复杂度的变体吗？我的变体有复杂度O(logN).

我的实施变体:

public class Dictionary {
    private static final int BIGGEST_TOP_MASK = 0xF00000;
    private static final int LESS_TOP_MASK = 0x0F0000;
    private static final int FULL_MASK = 0xFFFFFF;
    private String[] data;
    private static final int STEP = 100; // for real test step should be Integer.MAX_VALUE
    private int shiftIndex = -1;
    private static final int LESS_MASK = 0x0000FF;
    private static …

在实现插入排序时,可以使用二进制搜索来定位要插入元素i的数组的第一个i-1元素内的位置.

这将如何影响所需的比较次数？如何使用这样的二进制搜索影响Insertion Sort的渐近运行时间？

我很确定这会减少比较次数,但我不确定为什么.

我听说可以在O(n)时间内在双向链表上实现二进制搜索.访问双向链表的随机元素需要O(n)时间,二进制搜索访问O(log n)个不同的元素,所以运算符不应该是O(n log n)吗？

我正在看List,我看到一个带有一些重载的BinarySearch方法,我不禁想知道在List中有这样的方法是否有意义？

除非列表已排序,否则为什么我要进行二进制搜索？如果列表没有排序,调用该方法只会浪费CPU时间.在List上使用该方法有什么意义？

在文章http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binarySearch中,作者讨论了二进制搜索.他区分了找到某些东西是真的最低值,以及某些东西是假的最高值.被搜索的数组看起来像:

false false false true true

我很好奇为什么这两个案例不同.为什么你不能找到真实的最低值,然后减去一个找到最高值,这是假的？

Edit2:好的,所以我理解下限和下限.现在,我正在努力理解,当搜索大于或等于查询的最小整数时,为什么我们不能只改变if(mid>query)to if(mid>=query)并让它更低而不是上限.

编辑:这是文章所说的内容:

"现在我们终于找到实现二进制搜索的代码,如本节和前一节所述:

binary_search(lo, hi, p):
   while lo < hi:
      mid = lo + (hi-lo)/2
      if p(mid) == true:
         hi = mid
      else:
         lo = mid+1

   if p(lo) == false:
      complain                // p(x) is false for all x in S!

   return lo         // lo is the least x for which p(x) is true

...

如果我们想要找到p(x)为假的最后一个x,我们将设计(使用与上面类似的基本原理)类似于:

binary_search(lo, hi, p):
   while lo < hi:
      mid = lo + (hi-lo+1)/2 …