标签: binary-search

我看了一些BST代码,我可以看到每个节点都是一个结构.这有必要吗？

我不知道术语"懒惰"二进制搜索是否有效,但我正在阅读一些旧资料,我只是想知道是否有人可以解释懒惰二进制搜索的算法并将其与非惰性二进制文件进行比较搜索.

比方说,我们有这一系列的数字:

2, 11, 13, 21, 44, 50, 69, 88

如何11使用Lazy Binary Search查找号码？

希望有人知道这个Java认证问题的答案:

public static void main(String[] args) {
 String[] sa = {"d", "c", "a", "b" };
 int x = Arrays.binarySearch(sa, "b");
 Arrays.sort(sa);
 int y = Arrays.binarySearch(sa, "b");
 System.out.println(x + " " + y);
}

哪两个结果可能？(选择两项.)
A)7 0
B)7 1
C)7 3
D)-1 0
E)-1 1
F)-1 3

唯一真正的答案是E)-1 1,因为如果你玩二进制搜索算法,这是唯一可能的输出.但他们希望我选择两个...所以第二个必须是B)7 1然后,因为排序数组中的第二个二进制搜索将始终返回1.

所以我的问题是,为什么B)7 1可能的结果？更具体:如何可能,未排序数组中的第一个二进制搜索返回7？

提前致谢

我正在尝试实现二进制搜索.这是我的代码:

#!/usr/bin/perl
#use strict;
use warnings;

@array = (1..100);
$number = <STDIN>;
$low = 0;
$high = $#array;

while($low < $high){
    print "Searcing $low ---- $high \n";
    $mid = $low + ($high - $low)/2;
    if($array[$mid] == $number){
        print "Found in index:" . $mid;
        last;
    }
    elsif($array[$mid] < $number){
        $low = $mid + 1;
    }
    else{
        $high = $mid - 1;
    }   
}

但它不起作用,虽然它是一个直接的实现(至少它将在Java中).
似乎我在分割时得到浮点值并且无法搜索.如果我提供输入,5我会得到垃圾:

5  
Searcing 0 ---- 99  
Searcing 0 ---- 48.5  
Searcing 0 ---- 23.25  
Searcing …

我想找到整数数组中第一个整数的索引,它是<= key.我可以在log2(N)+1比较中使用二进制搜索来完成.不应该只用log2(N)比较吗？

// Returns the index of the first integer in keys <= key. size must be a power of 2.
unsigned find(int key, int* keys, unsigned size) {    
    int* origKeys = keys;

    for (int i = 0; i < log2(size); i++) {
        size /= 2;

        if (keys[size] < key)
            keys += size;
    }

    unsigned i = unsigned(keys - origKeys);
    // Not only is this step messy, because it doesn't fit the loop, but
    // now we have …

对于我的班级,我需要制作一个既使用二分搜索又使用线性搜索的程序.线性搜索工作正常,所以我知道问题不在于不存在所需的搜索词.

我试图找到答案,但这似乎是一个非常独特的问题.

我正在从文件中读取书籍列表并将其放入存储标题和ID号的自定义Books类中的数组中.我正在搜索身份证号码,每当身份证号码为奇数时,它就可以正常工作; 如果是偶数,则会产生无限循环.

这是有问题的代码.

private String binarySearch(String indexNumber){

    int left, middle, right, compare;
    String book = null;
    Boolean found = false;

    left = 0;
    right = list.length -1;

    while (found == false) {
        middle = (left + right) / 2;
        compare = list[middle].index.compareTo(indexNumber);

        if (compare == 0) {
            book = list[middle].title;
            found = true;
        } else {
            if (compare > 0) {
                right = middle - 1;
                System.out.println("New Right: " + right);
            } else {
                left = middle + …

我在一个案例中得到List.BinarySearch的奇怪结果.在列出"$ in"的列表中搜索"$ in"时,结果为-4.以下是一个突出问题的测试用例.只有寻找"$ in"的情况才会失败.

它可能是某种保留关键字吗？我编译了.Net Framworks 3.5,4.5.2和4.6,结果相同.

[TestMethod]
public void IssueWithBinarySearch() {
  List<string> operators = new List<string>( new[] { "$eq", "$gt", "$gte", "$lt", "$lte", "$ne", "$in", "$nin" } );

  Assert.AreEqual( 0, operators.BinarySearch( "$eq" ) );
  Assert.AreEqual( 1, operators.BinarySearch( "$gt" ) );
  Assert.AreEqual( 2, operators.BinarySearch( "$gte" ) );
  Assert.AreEqual( 3, operators.BinarySearch( "$lt" ) );
  Assert.AreEqual( 4, operators.BinarySearch( "$lte" ) );
  Assert.AreEqual( 5, operators.BinarySearch( "$ne" ) );
  Assert.AreEqual( 6, operators.BinarySearch( "$in" ) );
  Assert.AreEqual( 7, operators.BinarySearch( "$nin" ) );
}

所以我第一次尝试递归,在Python 3中编写一个简单的二进制搜索算法.运行我的程序后,我得到了这个错误:调用Python对象时超出了最大递归深度我做了一些研究,它说要添加这个线: sys.setrecursionlimit(40000)

我做了什么.当我输入不在我的列表中的数字时,我得到此分段错误错误.我读过这篇文章从我在Python中收集到的深度递归耗尽了内存？

我无法想象Python中不支持深度递归？无论如何,这是我的代码:

import sys

arr = [5, 17, 23, 33, 39, 44, 58, 62, 70, 74, 82, 99]
end = len(arr)
sys.setrecursionlimit(40000)

def binarySearch(arr, start, end,  x):

   #print("This is end: {}".format(end))
    mid = int((end + start)/2)
    #print("This is start {}".format(start))
    #print("This is end {}".format(end))
    #print("This is mid {}".format(mid))

    if x == arr[mid]:
        return x
    elif (x < arr[mid]):
        start = 0
        end = mid - 1
        return binarySearch(arr, start, end, x)
    else: # if x …

我有一个问题,我的二进制搜索算法找到2的平方根似乎是在一个无限循环并永远运行:

num = 2
low = 1
high = num
i = 0
while((i**2) != 2): #was while(low<high): but wasnt working with it either
 i = low + (high - low) / 2;

 sqrt = i * i

 if (sqrt == num):
     print(i)
 elif(sqrt < num):
     low = i
 else:
     high = i
print(sqrt)    

testRoot = 2 ** (.5)
print(testRoot)

我不确定我的while循环是否存在问题.我认为这将是一个非常直接的二进制搜索算法,稍作修改以适应平方根方面.

在运行我的代码时,我似乎无法让它产生任何输出.我不确定代码或编译器是否存在真正的问题,因为我认为我的算法与我过去的算法非常接近.

我正在尝试编写一个(更高阶函数),它接受一个向量和一个函数,并根据该函数进行二进制搜索,即如果它返回-1,我们需要更低,为1 - 更高,为0我们找到了合适的地方.我想出了类似的东西,但似乎我把函数作为参数传递出错了:

(defun bin-search (ls fpred)
 (let ((l (length ls))
       (x (aref ls (floor (length ls) 2))))
       (labels (binsearch (ls fpred l m)
                (case (funcall #'fpred (aref ls m))
                 (-1 (binsearch (ls fpred l (floor (- m l) 2))))
                 (0 (return-from binsearch m))
                 (1 (binsearch (ls fpred m (+ m (floor (- m l) 2)))))))
 (binsearch ls fpred 0 l))))

编译器说变量FPRED已定义但从未使用过.怎么了？