标签: binary-search

我知道在二叉搜索树上的有序遍历(VISIT LEFT,VISIT ROOT,VISIT RIGHT)给出了一个排序结果.但我需要在二叉树上进行后序遍历(VISIT LEFT,VISIT RIGHT,VISIT ROOT),结果应该给出排序值.

为了实现这一点,我应该如何构建我的二叉树？

String[] sortedArray = new String[]{"Quality", "Name", "Testing", "Package"};   

// Search for the word "cat" 
int index = Arrays.binarySearch(sortedArray, "Quality");  

我总是得到-3.问题在于"Name".为什么我不能"Name"进入我的阵列？任何的想法？

在TreeSet中有一个名为contains的方法,如果元素在集合中,则返回true.我假设此方法使用二进制搜索,并不按升序迭代所有元素.我对吗？

我有一个TreeSet,它包含一个类的对象,该类使用两个String实例变量来区分它与同一个类的其他对象.我希望能够通过比较两个实例变量(当然使用get方法)和另外两个String变量来创建一个搜索TreeSet的方法,如果它们相等,则返回该元素.如果实例变量小于转到右子树中的第一个元素,或者如果它们在左子树中搜索更大等等.有没有办法做到这一点？

我知道我可以将对象存储在ArrayList中并使用二进制搜索来查找对象,但这不会像搜索TreeSet那么快.

当我试图将它应用到现实世界时,二进制搜索让我失望.方案如下.

我需要测试通过无线电通信的设备的范围.通信需要快速进行,但传输速度慢,可达到一定程度(例如,大约3分钟).我需要测试传输是否每200英尺成功一次,直到失败,最多1600英尺.每200英尺将进行一次测试,需要3分钟才能执行.

我天真地认为二元搜索是找到故障点的最有效方法,但考虑到200英尺/分钟的行进速度和3分钟的测试时间.如果在500英尺处发生传输失败,二进制搜索不是找到故障点的最有效方法,如下所示.

只需走路并测试每一个点就可以更快地找到解决方案,只需12分钟,而二进制搜索和测试则需要16分钟.

我的问题:在旅行时间问题上,您如何计算解决方案的最有效途径？这叫什么(例如,二元旅行搜索等)？

我正在尝试使用以下函数实现二进制搜索:

def buggy_binary_search(input, key):
    low = 0
    high = len(input)-1
    mid = (low + high)/2
    while low <= high:
        if input[mid] == key:
            return mid
        if input[mid] > key:
            high = mid - 1
        else:
            low = mid
    return -1

运行时的上述函数进入无限循环.我怎么能纠正这个？

我正在尝试编写一个二进制搜索,它采用排序列表并找到小于目标值的最大数字:

def binary_max(list, target)
    hi=len(list)-1
    lo=0
    while lo<=hi:
        mid=(hi+lo)//2
        midval=list[mid]
        if midval > target:
            hi=mid-1
        elif midval <= target:
            lo=mid
        if hi==lo:
            break
    return(list[mid])
pass

但是,例如,当有一个长度为2的列表时,hi = 1并且中间值总是卡在lo上,无论如何都要避免这个问题？

谢谢

我正在学习算法/大o,我只是对此感到好奇.

指某东西的用途

 mid = (low+high)/2;

为了获得二进制搜索算法的中点,通常不鼓励因为可能存在溢出错误.为什么会导致溢出错误,怎么办？

 mid = low + (high-low)/2;

防止这个错误？

谢谢.

这里有一个例子:

DT = data.table(x=1:4, y=6:9, z=3:6)
setkey(DT, x, y)

连接列有多个值:

xc = c(1, 2, 4)
yc = c(6, 9)
DT[J(xc, yc), nomatch=0]
   x y z
1: 1 6 3

这种使用J()只返回单行.实际上,我想加入%in%运营商.

DT[x %in% xc & y %in% yc]
   x y z
1: 1 6 3
2: 4 9 6

但是使用%in%运算符使搜索成为矢量扫描,与二进制搜索相比,这是非常慢的.为了进行二进制搜索,我构建了每个可能的连接值组合:

xc2 = rep(xc, length(yc))
yc2 = unlist(lapply(yc, rep, length(xc)))
DT[J(xc2, yc2), nomatch=0]
   x y z
1: 1 6 3
2: 4 9 6

但是以这种方式构建xc2,yc2会使代码难以阅读.%in% …

我有一个包含大约200,000条记录的file.txt.

每条记录的格式为123456-99-Text.123456是唯一的帐号,99是我需要的位置代码(从01更改为99),文本无关紧要.这些帐号按顺序排序,并在每个交流的文件中有换行符(111111,11111,1111113等).

我制作了一个视觉工作室文本框和搜索按钮,让某人搜索帐号.帐号实际上是11位数,但只有前6位.我把它写成字符串actnum = textbox1.text.substring(0,6)

我写了一个foreach (string x in file.readline('file.txt'))与if (x.contains(actnum))随后string code = x.substring(8,2))的发言.

该程序运行良好,但因为有很多记录,如果有人搜索不存在的帐号,或列表底部的数字,程序会锁定好10秒钟,然后再转到"未找到号码"否则声明,或永远找到最后一条记录.

我的问题:

阅读二进制搜索我试图尝试一个没有太大成功.我似乎无法使数组或文件像合法的二进制搜索一样.有没有办法从textbox1中取出6位数的actnum,将它与6位数帐号的数组子串进行比较,然后从该特定行中获取子串99代码？

二进制搜索会有很大帮助!我可以拿555-555并将其与记录文件的上半部分或下半部分进行比较,然后继续搜索直到我对我需要的线路进行搜索,抓住整条线,然后将99输出.我遇到的问题是我似乎无法获得文件的正确整数转换,因为它包含数字和文本,因此我无法正确使用<,>,=符号.

任何有关这方面的帮助将不胜感激.我目前的程序实际上有效,但有时非常慢.

每当我迭代地执行二进制搜索时,我总是很困惑我是否应该使用while (low < high)或while(low <= high).

虽然两者都有效但有人能告诉我一个人的实际优势是什么？