标签: binary-search

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

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

我需要帮助编写一个使用二进制搜索的程序来递归计算输入非负整数的平方根(向下舍入到最接近的整数).

这是我到目前为止:

import java.util.Scanner;

public class Sqrt {

  public static void main(String[] args) {

    Scanner console = new Scanner(System.in);

    System.out.print("Enter A Valid Integer: ");

    int value = console.nextInt();

    calculateSquareRoot(value);

  }

    public static int calculateSquareRoot(int value) {
      while (value > 0) {
      double sqrt = (int) Math.sqrt(value);
      System.out.println(sqrt);
    }
    return -1;
    }
}

它必须使用二进制搜索来计算平方根这一事实让我感到困惑.如果有人对如何做到这一点有任何建议,将不胜感激.谢谢

我试图在python中实现二进制搜索,并编写如下.但是,只要needle_element大于数组中的最大元素,我就无法停止.

你能帮我吗？谢谢.

def binary_search(array, needle_element):
    mid = (len(array)) / 2
    if not len(array):
        raise "Error"
    if needle_element == array[mid]:
        return mid
    elif needle_element > array[mid]:
        return mid + binary_search(array[mid:],needle_element)
    elif needle_element < array[mid]:
        return binary_search(array[:mid],needle_element)
    else:
        raise "Error"

在文章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 …

我无法以最佳方式解决以下问题,也无法找到在任何地方执行此操作的方法.

给定N×M矩阵,其中每行被排序,找到矩阵的整体中值.假设N*M是奇数.

例如,

矩阵=
[1,3,5]
[2,6,9]
[3,6,9]

A = [1,2,3,3,5,6,6,9,9]

中位数为5.因此,我们返回5.
注意:不允许额外的内存.

任何帮助将不胜感激.

这是Robert Sedgewick的算法第4版的练习题1.4.24.

Suppose that you have an N-story building and plenty of eggs. Suppose also that
an egg is broken if it is thrown off floor F or higher, and unhurt otherwise.
First, devise a strategy to determine the value of F such that the number of
broken eggs is ~lgN when using ~lgN throws, then find a way to reduce the cost to
~2lgF.

虽然lgN解决方案很容易想到,但我完全不知道2lgF解决方案.无论如何,我们没有给出价值F,所以2lgF解决方案的基础是什么？

谁能对这个问题有所了解？谢谢.

python是否提供在排序列表上执行二进制搜索的功能,类似于C++标准库的算法std::lower_bound和std::upper_bound算法？

我刚刚开始学习并行编程,我正在研究二进制搜索.

通过投入更多的处理器,这无法真正优化吗？我知道这应该是分裂和征服,但你真的"正在减少和征服"(来自维基百科).

或者你可以将这些比较并行化吗？(如果X是小于array[mid],从搜索low到mid - 1;否则,如果X是大于array[mid]从搜索mid + 1到high,否则返回mid,的指数X)

或者你将一半的数组放到一个处理器上进行二进制搜索,另一半到另一个处理器怎么样？这不是浪费吗？因为它正在减少和征服而不是简单地分裂和征服？思考？

我有一个对象列表排序,我想找到一个对象的第一次出现和最后一次出现.在C++中,我可以轻松地使用std :: equal_range(或者只使用一个lower_bound和一个upper_bound).

例如:

bool mygreater (int i,int j) { return (i>j); }

int main () {
  int myints[] = {10,20,30,30,20,10,10,20};
  std::vector<int> v(myints,myints+8);                         // 10 20 30 30 20 10 10 20
  std::pair<std::vector<int>::iterator,std::vector<int>::iterator> bounds;

  // using default comparison:
  std::sort (v.begin(), v.end());                              // 10 10 10 20 20 20 30 30
  bounds=std::equal_range (v.begin(), v.end(), 20);            //          ^        ^

  // using "mygreater" as comp:
  std::sort (v.begin(), v.end(), mygreater);                   // 30 30 20 20 20 10 10 10
  bounds=std::equal_range (v.begin(), v.end(), 20, mygreater); …

二进制搜索可以通过多种方式实现 - 递归,迭代,条件等.我从Bentley的书" 编程珍珠:编写正确的程序"中获取了这一点,这是一个迭代实现,其中包含一个错误.

 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中发现了一个错误; 它可能导致溢出.我们怎样才能避免这种二进制搜索中的溢出？