标签: binary-search

我注意到,从Ruby 2.0.0开始,数组类有一个bsearch我正在测试的方法,而且我没有得到我期望的行为.为什么它返回2和5的值,但是nil-1,1和4？

arr_in = [-1, 1, 2, 4, 5]

arr_in.bsearch { |x| x == 3 }   #=> nil
arr_in.bsearch { |x| x == -1 }  #=> nil
arr_in.bsearch { |x| x == 1 }   #=> nil
arr_in.bsearch { |x| x == 2 }   #=> 2
arr_in.bsearch { |x| x == 4 }   #=> nil
arr_in.bsearch { |x| x == 5 }   #=> 5

您好,下面是我的二进制搜索实现的伪代码:

Input: (A[0...n-1], K)
begin
   l ? 0; r ? n-1
   while l ? r do
      m ? floor((l+r)/2)
      if K > A[m] then l ? m+1
      else if K < A[m] then r ? m-1 else return m
      end if 
   end while
   return -1 // key not found
end

我只是想知道如何计算这个实现在最坏情况下对大小为n的排序数组进行的比较次数？

比较次数是否= lg n + 1？还是别的什么？

我有一个已旋转的排序列表,并希望在该列表上进行二进制搜索以找到最小元素.

让我们假设初始列表是{1,2,3,4,5,6,7,8},旋转列表可以像{5,6,7,8,1,2,3,4}

在这种情况下,正常的二进制搜索不起作用.知道如何做到这一点.

- 编辑

我有另一个条件.如果列表没有排序怎么办？

我使用lambda表达式来排序和搜索C#中的数组.我不想在我的类中实现IComparer接口,因为我需要对多个成员字段进行排序和搜索.

class Widget
{
    public int foo;

    public void Bar()
    {
        Widget[] widgets;

        Array.Sort(widgets, (a, b) => a.foo.CompareTo(b.foo));

        Widget x = new Widget();
        x.foo = 5;
        int index = Array.BinarySearch(widgets, x,
                                       (a, b) => a.foo.CompareTo(b.foo));
    }
}

虽然排序工作正常,但二进制搜索会产生编译错误无法将lambda表达式转换为类型'System.Collections.IComparer <Widget>',因为它不是委托类型.由于某种原因,Sort对IComparer和Comparison都有重载,但BinarySearch只支持IComparer.经过一些研究,我发现ComparisonComparer<T>将比较转换为IComparer 的笨重:

public class ComparisonComparer<T> : IComparer<T>
{
    private readonly Comparison<T> comparison;

    public ComparisonComparer(Comparison<T> comparison)
    {
        this.comparison = comparison;
    }

    int IComparer<T>.Compare(T x, T y)
    {
        return comparison(x, y);
    }
}

这允许二进制搜索如下工作:

int index = Array.BinarySearch(
  widgets,
  x, …

我被问到二元搜索是否是考试中的分而治之算法.我的回答是肯定的,因为你将问题分成了较小的子问题,直到你达到了结果.

但是检查员询问其中的征服部分在哪里,我无法回答.他们也不赞成它实际上是一种分而治之的算法.

但是我到网上的所有地方都说它是,所以我想知道为什么,以及征服它的部分在哪里？

我的任务是创建一个方法,打印所有索引,其中值x在排序数组中找到.

据我所知,如果我们只是从0到N(数组的长度)扫描数组,它将有一个O(n)最坏情况的运行时间.由于将传递给方法的数组将被排序,我假设我可以利用二进制搜索,因为这将是O(log n).但是,这仅在数组具有唯一值时才有效.由于二进制搜索将在第一次"查找"特定值之后完成.我正在考虑进行二进制搜索以在排序数组中查找x,然后检查此索引之前和之后的所有值,但是如果数组包含所有x值,那么它似乎不会好得多.

我想我要问的是,有没有更好的方法来找到排序数组中特定值的所有索引,这些索引优于O(n)？

public void PrintIndicesForValue42(int[] sortedArrayOfInts)
{
    // search through the sortedArrayOfInts

    // print all indices where we find the number 42. 
}

例如:sortedArray = {1,13,42,42,42,77,78}将打印:"在指数中发现42:2,3,4"

二分搜索对于均匀分布非常有效.列表中的每个成员具有相同的"命中"概率.这就是你每次尝试中心的原因.

没有统一分布的有效算法吗？例如,1/x分布之后的分布.

在(已经)排序上进行二进制搜索的最简单方法是什么NSArray？

到目前为止我发现的一些潜在方法包括:

1. 使用CFArrayBSearchValues(这里提到) - 这会起作用NSArray吗？

2. 该方法indexOfObject:inSortedRange:options:usingComparator:的NSArray假定数组进行排序,并采取一种opts类型的PARAM NSBinarySearchingOptions-这意味着它执行二进制搜索？该文档只是说:

   返回对象的指定范围内的索引与使用给定NSComparator块的数组中的元素进行比较.

3. 编写我自己的二进制搜索方法(类似于此).

我应该补充一点,我正在为iOS 4.3+编程

提前致谢.

有一个数组,可以包含,例如,最多1000元素.它可以产生的数字范围1 to 10^10.现在我必须minimal absolute difference在数组中找到两个数字之间的数字.我想到了两种算法:

对于第一个,我已经定义了一个binarysearch函数,该函数在排序的数组中找到要插入的数字的位置.现在,我只使用给定数组的第一个数字启动排序数组,然后从第二个元素开始迭代给定数组.对于每个数字,我在排序数组中找到它的位置.如果该位置的数字是这个数字,那么差值为0,它是最低的数字,所以我退出循环.否则,我在该点插入已排序数组中的数字,然后检查该数字与该数组中前一个和下一个数字之间的差异.然后我存储此结果的最小值和先前的结果,并以这种方式继续.

第二:我使用quicksort对数组进行排序.(范围太大,所以我认为基数排序不会那么高效).然后我迭代它,如果两个连续的数字相等则以0的答案断开,否则存储该数字与前一个数字和前一个结果之间的差值的最小值.

哪一个会更有效率？

还有更好的算法吗？

Stackoverflow在这方面有很多帖子,但它们没有多大帮助.这是我在Perl中的代码:

sub position {
    my @list   = @{$_[0]};
    my $target = $_[1];

    my ($low,$high) = (0, (scalar @list)-1);

    while ($low <= $high) {
        $mid = int(($high + $low)/2);

        if ( $list[$mid] == $target ) {

            return $mid;
        }
        elsif ( $target < $list[$mid] ) {

            $high = $mid - 1; 
        }
        else {

            $low = $mid + 1;
        }
    }
    $low; …

(sharth的评论已经回答了.)

我在python中编写了一个二进制搜索算法,它或多或少遵循与bisect模块中的bisect_left函数相同的结构.实际上它有一些较少的条件,因为我知道高点将是列表的长度而低值将为0.但由于某种原因,内置函数的运行速度是我的5倍.

我的代码如下:

def bisection_search(word, t):

    high = len(t)
    low = 0

    while low < high:
        half = (high+low)/2
        if t[half] < word:
            low = half + 1
        else:
            high = half
    return low

内置函数的源代码是:

def bisect_left(a, x, lo=0, hi=None):
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] < x: lo = mid+1
        else: hi = mid
    return lo

如你所见,几乎完全相同.然而,我的函数的超时时间(在100,000字的有序列表中搜索最后一个项)是-3.60012054443e-05,其中内置达到-6.91413879395e-06.是什么解释了这种差异

在源代码中,最后有一条注释说"用快速C实现覆盖上面的定义" …