现在我需要修改搜索算法,以便返回所有匹配的列表项。应该如何最好地做到这一点?
好的,由于列表已经排序,你感兴趣的所有条目都是连续的。这意味着你需要从二分搜索产生的索引开始向后查找第一个等于找到项的条目。最后一个条目也是同样的方法。
你可以简单地从找到的索引开始向后查找,但是如果有很多与找到项相等的项,这种解决方案可能会变得像O(n)一样慢。因此,你最好使用指数搜索:在找到更多匹配项时,使跳跃翻倍。这样,整个搜索仍然是O(log n)。
首先让我们回想一下简单的二分查找代码片段:
int bin_search(int arr[], int key, int low, int high)
{
if (low > high)
return -1;
int mid = low + ((high - low) >> 1);
if (arr[mid] == key) return mid;
if (arr[mid] > key)
return bin_search(arr, key, low, mid - 1);
else
return bin_search(arr, key, mid + 1, high);
}
引用自Skiena教授: 如果我们从上面的实现中删除相等测试 if(s[middle] == key) 返回(middle); 并在每次不成功的搜索中返回索引low而不是-1。由于没有相等测试,所有搜索现在都将失败。 当关键字与相同的数组元素进行比较时,搜索将继续到右半部分,最终在右边界处终止。 在二进制比较方向反转后重复搜索将导致我们达到左边界。每次搜索都需要O(lgn)时间, 因此,无论块的大小如何,我们可以在对数时间内计算出发生的次数。
因此,我们需要两轮二分搜索来找到lower_bound(查找第一个不小于KEY的数)和upper_bound(查找第一个大于KEY的数)。
int lower_bound(int arr[], int key, int low, int high)
{
if (low > high)
//return -1;
return low;
int mid = low + ((high - low) >> 1);
//if (arr[mid] == key) return mid;
//Attention here, we go left for lower_bound when meeting equal values
if (arr[mid] >= key)
return lower_bound(arr, key, low, mid - 1);
else
return lower_bound(arr, key, mid + 1, high);
}
int upper_bound(int arr[], int key, int low, int high)
{
if (low > high)
//return -1;
return low;
int mid = low + ((high - low) >> 1);
//if (arr[mid] == key) return mid;
//Attention here, we go right for upper_bound when meeting equal values
if (arr[mid] > key)
return upper_bound(arr, key, low, mid - 1);
else
return upper_bound(arr, key, mid + 1, high);
}
希望它有所帮助 :)
{1,2,2,3,4,5,5,5,6,7,8,8,9}
。普通的搜索会命中与 5 相比较的某个对象,但是您想要获取它们所有的值,对吗? range search (type *array) {
int index = bsearch(array, 0, array.length-1);
// left
int upperBound = index -1;
int i = upperBound;
do {
upperBound = i;
i = bsearch(array, 0, upperBound);
} while (i != -1)
// right
int lowerBound = index + 1;
int i = lowerBound;
do {
lowerBound = i;
i = bsearch(array, lowerBound, array.length);
} while (i != -1)
return range(lowerBound, UpperBound);
}
这段Java代码可以在一次遍历中以O(logN)时间计算已排序数组中目标值的出现次数。很容易将其修改为返回找到的索引列表,只需传入ArrayList。
思路是递归地缩小e
和b
边界,直到它们成为具有目标值的连续块的下限和上限;
static int countMatching(int[] arr, int b, int e, int target){
int m = (b+e)/2;
if(e-b<2){
int count = 0;
if(arr[b] == target){
count++;
}
if(arr[e] == target && b!=e){
count++;
}
return count;
}
else if(arr[m] > target){
return countMatching(arr,b,m-1, target);
}
else if(arr[m] < target){
return countMatching(arr, m+1, e, target);
}
else {
return countMatching(arr, b, m-1, target) + 1
+ countMatching(arr, m+1, e, target);
}
}
equal_range
方法一次性生成所需结果。为了加快Java和.NET中搜索的速度,当等值范围太长以至于无法线性迭代时,您可以寻找前驱元素和后继元素,并取范围中间的值,不包括两端。
如果由于进行第二个二分查找而导致速度过慢,请考虑编写自己的搜索,同时查找两端。这可能有点繁琐,但应该运行得更快。
equal_range
翻译成你选择的语言也不应该太难。 - Sergey Kalinichenko首先,根据可排序属性(使用“正常”二分查找),找到单个元素的索引,然后开始查找该元素在列表中左右两侧的所有元素,将所有符合搜索条件的元素添加到结果中,在某一端时停止搜索,当一个元素不符合条件或没有更多元素可遍历时停止搜索,并在左右两端同时满足上述停止条件时完全停止搜索。
以下是 Deril Raju(上面的答案中)提供的解决方案,移植到 Swift 中:
func bin_search(_ A: inout [Int], first: Int, last: Int, key: Int, searchLow: Bool) -> Int {
var result = -1
var low = first
var high = last
while low <= high {
let mid = (low + high) / 2
if A[mid] < key {
low = mid + 1
} else if A[mid] > key {
high = mid - 1
} else {
result = mid
if searchLow {
high = mid - 1 // go on searching towards left (lower indices)
} else {
low = mid + 1 // go on searching towards right (higher indices)
}
}
}
return result
}
func bin_search_range(_ A: inout [Int], first: Int, last: Int, key: Int) -> (Int, Int) {
let low = bin_search(&A, first: first, last: last, key: key, searchLow: true)
let high = bin_search(&A, first: first, last: last, key: key, searchLow: false)
return (low, high)
}
func test() {
var A = [1, 2, 3, 3, 3, 4, 4, 4, 4, 5]
assert(bin_search(&A, first: 0, last: A.count - 1, key: 3, searchLow: true) == 2)
assert(bin_search(&A, first: 0, last: A.count - 1, key: 3, searchLow: false) == 4)
assert(bin_search_range(&A, first: 0, last: A.count - 1, key: 3) == (2, 4))
assert(bin_search(&A, first: 0, last: A.count - 1, key: 4, searchLow: true) == 5)
assert(bin_search(&A, first: 0, last: A.count - 1, key: 4, searchLow: false) == 8)
assert(bin_search_range(&A, first: 0, last: A.count - 1, key: 4) == (5, 8))
assert(bin_search_range(&A, first: 0, last: A.count - 1, key: 5) == (9, 9))
assert(bin_search_range(&A, first: 0, last: A.count - 1, key: 0) == (-1, -1))
}
test()