在循环元素序列中定位第一个元素的最快方法
在循环元素序列中定位第一个元素的最快方法
提问于 2015-08-11 23:34:02
我编写了这个二进制搜索函数，以在索引序列中定位特定的值：
def locate(xs: IndexedSeq[Int], x: Int, l: Int, h: Int): Int = {
(l + h) / 2 match {
case m if h - l <= 1 => l
case m if x >= xs(m) => locate(xs, x, m, h)
case m => locate(xs, x, l, m)
}
}当我有一个序列时，它可以工作，例如：
Vector(1,2,3,9,15,26,89)也就是唯一元素的有序序列。但是，当有序序列中有重复元素时，它不起作用，如：
Vector(1,2,3,3,15,15,89)不能保证选择循环子序列的第一个元素。例如，如果我想搜索3，它可能不会给出序列中前3的索引。
哪种算法能有效地做到这一点？或者，我可以修改我的二进制搜索序列，使我可以很容易地做到这一点(同时仍然是尾递归)。
回答 1
Stack Overflow用户
回答已采纳
发布于 2015-08-12 00:01:40
基于定界的算法，我认为这种更改就足够了：
def locate(xs: IndexedSeq[Int], x: Int, l: Int, h: Int): Int = {
l+(h-l)/2 match {
case m if h - l == 0 => l
case m if xs(m) < x => locate(xs, x, m+1, h)
case m => locate(xs, x, l, m)
}
}我还更改了计算m的代码，因为在极端情况下，原始代码容易发生整数溢出。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/31953715
复制相关文章
相似问题
腾讯云开发者
