标签: binary-search

这困扰了我一段时间.我知道,如果N键以二叉搜索树的形式排列,可以创建的树的可能数量对应于加泰罗尼亚序列中的第N个数字.

我一直试图确定这是为什么; 无法找到任何甚至可能试图直观地解释它的东西我诉诸于SO的集体知识.我找到了计算可能树木数量的其他方法,但它们似乎不太直观,除了如何使用它之外没有提供任何解释.加上维基页面(上面的链接)甚至可以显示带有3个键的可能树形图的图像,这将使我认为有一个很好的和整洁的解释可以被听到(不用说,不包括在文章中) ).

提前致谢!

我正在修改一些代码,我意识到我从来不知道的事情.正常的二进制搜索将在数据集中返回多次出现的键的随机索引.如何修改下面的代码以返回第一次出现？这是人们做的事吗？

//ripped from the JDK
public static int binarySearchValue(InvertedContainer.InvertedIndex[] a, long key) {
    return bSearchVal(a, 0, a.length, key);
}

private static int bSearchVal(InvertedContainer.InvertedIndex[] a, int fromIndex,
                                 int toIndex, long key) {
    int low = fromIndex;
    int high = toIndex - 1;

    while (low <= high) {
        int mid = (low + high) >>> 1;
        long midVal = a[mid].val;

        if (midVal < key)
            low = mid + 1;
        else if (midVal > key)
            high = mid - 1;
        else …

我使用标准二进制搜索来快速返回排序列表中的单个对象(相对于可排序属性).

现在我需要修改搜索,以便返回所有匹配列表条目.我该怎么做才能做到最好？

我有一个python 3.x程序产生错误:

def main():
    names = ['Ava Fischer', 'Bob White', 'Chris Rich', 'Danielle Porter',
             'Gordon Pike', 'Hannah Beauregard', 'Matt Hoyle',
             'Ross Harrison', 'Sasha Ricci', 'Xavier Adams']

    entered = input('Enter the name of whom you would you like to search for:')
    binary_search(names, entered)

    if position == -1:
        print("Sorry the name entered is not part of the list.")
    else:
        print(entered, " is part of the list and is number ", position, " on the list.")
    input('Press<enter>')

def binary_search(names, entered):
    first = 0 …

我试图解决Hackerland无线电发射机编程问题.

总而言之,挑战如下:

Hackerland是一维城市Ñ房屋,其中每个房子我位于一些X _我在x轴上.市长希望在城市房屋的屋顶上安装无线电发射器.每个发射机具有一个范围,ķ,这意味着它可以将信号发送到所有的房屋≤ ķ单位距离的路程.

鉴于Hackerland的地图和k的值,您能找到覆盖每个房屋所需的最小数量的发射器吗？

我的实现如下:

package biz.tugay;

import java.util.*;

public class HackerlandRadioTransmitters {

    public static int minNumOfTransmitters(int[] houseLocations, int transmitterRange) {
        // Sort and remove duplicates..
        houseLocations = uniqueHouseLocationsSorted(houseLocations);
        int towerCount = 0;
        for (int nextHouseNotCovered = 0; nextHouseNotCovered < houseLocations.length; ) {
            final int towerLocation = HackerlandRadioTransmitters.findNextTowerIndex(houseLocations, nextHouseNotCovered, transmitterRange);
            towerCount++;
            nextHouseNotCovered = HackerlandRadioTransmitters.nextHouseNotCoveredIndex(houseLocations, towerLocation, transmitterRange);
            if (nextHouseNotCovered == -1) {
                break;
            } …

有没有办法在带有对象的ArrayList中实现二进制搜索？在此示例中,ArrayList将使用字段"id"进行排序.

class User{
 public int id;
 public string name;
}

ArrayList<User> users = new ArrayList<User>();

sortById(users);

int id = 66
User searchuser = getUserById(users,id);

如果我应该使用二进制搜索返回具有指定id的用户,那么"User getUserById(ArrayList users,int userid)"如何？这甚至可能吗？

以下是我从TopCoder关于二进制搜索的教程中得到的伪代码

binary_search(A, target):
   lo = 1, hi = size(A)
   while lo <= hi:
      mid = lo + (hi-lo)/2
      if A[mid] == target:
         return mid            
      else if A[mid] < target: 
         lo = mid+1
      else:
         hi = mid-1

   // target was not found

为什么我们计算中间值为mid = lo +(hi-lo)/ 2？(hi + lo)/ 2错了

我有一点想法,可能是为了防止溢出,但我不确定,也许有人可以向我解释,如果还有其他原因.

findInterval()R中的强大函数在其vec参数中使用左闭的子区间,如其文档中所示:

如果i <- findInterval(x,v),我们有v[i[j]] <= x[j] < v[i[j] + 1]

如果我想要右关闭的子间隔,我的选择是什么？我想出的最好的是:

findInterval.rightClosed <- function(x, vec, ...) {
  fi <- findInterval(x, vec, ...)
  fi - (x==vec[fi])
}

另一个也有效:

findInterval.rightClosed2 <- function(x, vec, ...) {
  length(vec) - findInterval(-x, -rev(vec), ...)
}

这是一个小测试:

x <- c(3, 6, 7, 7, 29, 37, 52)
vec <- c(2, 5, 6, 35)
findInterval(x, vec)
# [1] 1 3 3 3 3 4 4
findInterval.rightClosed(x, vec)
# [1] 1 2 3 3 …

我注意到,从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

C++ 11包括该算法std::partition_point().然而,对于我尝试过的所有情况,它给出了相同的答案std::lower_bound().唯一的区别是方便的T& value参数.

我错过了什么,或者这两个功能或多或少都做了同样的事情？