每个程序员都被教导二进制搜索是一种搜索有序数据列表的好方法.有许多玩具教科书使用二进制搜索的例子,但在实际编程中呢:在现实生活中程序中实际使用的二元搜索在哪里？
我们大多数人都熟悉最大和子阵列问题.我遇到了这个问题的一个变体,要求程序员输出模数为M的所有子阵列总和的最大值.
解决这种变体的天真方法是找到所有可能的子阵列总和(其数量为N ^ 2,其中N是数组的大小).当然,这还不够好.问题是 - 我们怎样才能做得更好？
示例:让我们考虑以下数组:
6 6 11 15 12 1
设M = 13.在这种情况下,子阵列6 6(或12或6 6 11 15或11 15 12)将产生最大总和(= 12).
我理解>>>修复了溢出:当添加两个大的正数时,你可能会得到一个负数.有人可以解释这种按位移位如何神奇地修复溢出问题吗？它有何不同>>？
我怀疑:我认为这与Java使用两个赞美这一事实有关,所以如果我们有额外的空间但溢出是正确的数字,但是因为我们没有它变成负面的.所以当你移动并用零划桨时,它会因为两个赞美而神奇地固定下来.但我可能是错的,有点大脑的人必须证实.:)
我们希望在复杂度不大于的循环排序数组中搜索给定元素O(log n).
示例:搜索13在{5,9,13,1,3}.
我的想法是将循环数组转换为常规排序数组,然后对结果数组进行二进制搜索,但我的问题是我提出的算法是愚蠢的,它O(n)在最坏的情况下采取:
for(i = 1; i < a.length; i++){
if (a[i] < a[i-1]){
minIndex = i; break;
}
}
那么第i个元素的相应索引将由以下关系确定:
(i + minInex - 1) % a.length
很明显,我的转换(从循环到常规)算法可能需要O(n),所以我们需要一个更好的.
根据ire_and_curses的想法,这是Java中的解决方案:
public int circularArraySearch(int[] a, int low, int high, int x){
//instead of using the division op. (which surprisingly fails on big numbers)
//we will use the unsigned right shift to get the average
int mid = (low + high) >>> 1; …是否存在比二进制搜索更快的算法,用于搜索数组的排序值？
在我的情况下,我有一个A数组中的排序值(可能是任何类型值),n如果我看的值在范围内,我需要返回A[n] and A[n+1]
给定一个整数数组,找到局部最小值.如果A [i-1]> A [i]和A [i] <A [i + 1],则元素A [i]被定义为局部最小值,其中i = 1 ... n-2.在边界元素的情况下,数量必须小于其相邻数字.
我知道如果只有一个局部最小值,那么我们可以用修改后的二进制搜索来解决.但是如果知道阵列中存在多个局部最小值,它能否及时解决O(log n)？
二分搜索和二叉搜索树有什么区别？
它们是一样的吗？阅读互联网似乎第二个仅适用于树(最多2个子节点),二分搜索不遵循此规则.我没理得.
我有一个包含整数键的字典.我想得到最大的钥匙.我不跟踪密钥,因此它们可能是连续的(例如1,2,3,4,5,6),但可能会跳过(1,3,4,5),尽管我怀疑这有什么不同.
我只是使用二分搜索还是有方法？据我所知,你几乎无法击败二元搜索这么简单的任务 - 也许你可以把它减半.
我有一个排序的数组,并希望对它进行二进制搜索.
所以我问Swift库中是否已有类似等等的东西？或者是否有可用的独立版本？
当然我可以自己写,但我想避免再次重新发明轮子.
我使用标准二进制搜索来快速返回排序列表中的单个对象(相对于可排序属性).
现在我需要修改搜索,以便返回所有匹配列表条目.我该怎么做才能做到最好？