我使用标准二分搜索快速返回排序列表中的单个对象（关于可排序属性）。
现在我需要修改搜索，以便返回所有匹配的列表条目。我应该如何最好地做到这一点？
问问题
44513 次
13 回答
27
好吧，随着列表的排序，您感兴趣的所有条目都是连续的。这意味着您需要找到与找到的项目相等的第一个项目，从二进制搜索产生的索引向后看。最后一项也是如此。
您可以简单地从找到的索引向后退，但是如果有很多项目等于找到的项目，这样解决方案可能会像 O(n) 一样慢。所以你应该更好地使用指数搜索：当你找到更多相等的项目时，你的跳跃加倍。这样你的整个搜索仍然是 O(log n)。
于 2012-08-27T15:28:04.583 回答
24
首先让我们回顾一下简单的二分搜索代码片段：
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);
}
引自 Prof.Skiena：假设我们删除相等测试 if (s[middle] == key) return(middle); 从上面的实现中返回索引低而不是每次不成功的搜索时的-1。现在所有搜索都将失败，因为没有相等性测试。每当将键与相同的数组元素进行比较时，搜索将继续到右半部分，最终在右边界处终止。在反转二进制比较的方向后重复搜索将引导我们到左边界。每次搜索都需要 O(lgn) 时间，因此无论块的大小如何，我们都可以以对数时间计算出现次数。
所以，我们需要两轮binary_search来找到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);
}
希望它有帮助:)
于 2014-09-22T03:06:34.877 回答
7
如果我在关注您的问题，您有一个对象列表，为了比较，看起来像{1,2,2,3,4,5,5,5,6,7,8,8,9}. 对 5 的正常搜索将命中比较为 5 的对象之一，但您想获取所有对象，对吗？
在这种情况下，我建议使用标准的二分搜索，在到达匹配元素时，开始向左看直到它停止匹配，然后再次向右（从第一个匹配）直到它停止匹配。
请注意，您使用的任何数据结构都不会覆盖相同的元素！
或者，考虑使用一种结构，该结构存储与该位置的存储桶相同的元素。
于 2012-08-27T15:24:27.367 回答
3
我会进行两次二进制搜索，一次查找第一个元素比较 >= 值（在 C++ 术语中，lower_bound），然后一个搜索第一个元素比较 > 值（在 C++ 术语中，upper_bound）。从 lower_bound 到上界之前的元素就是您要查找的元素（根据 java.util.SortedSet，subset(key, key)）。
因此，您需要对标准二分搜索进行两个不同的细微修改：您仍然探测并使用探测处的比较来缩小您要查找的值必须位于的区域，但现在例如对于 lower_bound 如果您遇到相等，所有您知道的是您正在寻找的元素（第一个相等的值）位于范围的第一个元素和您刚刚探测的值之间的某个位置 - 您不能立即返回。
于 2012-08-27T15:32:06.283 回答
3
一旦你找到了与 bsearch 的匹配，只需递归 bsearch 双方直到不再匹配
伪代码：
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);
}
但是没有涵盖极端情况。我认为这将使您的复杂性保持在（O（logN））。
于 2012-08-27T16:03:25.003 回答
2
我首先找到给定可排序属性的单个元素的索引（使用“正常”二进制搜索），然后开始查看列表中元素的左右两侧，添加找到的所有元素以满足搜索条件，当一个元素不满足条件或者没有更多元素可以遍历时在一端停止，当左右两端都满足前面提到的停止条件时完全停止。
于 2012-08-27T15:26:38.447 回答
2
这取决于您使用的二进制搜索的实现：
- 在 Java 和 .NET 中，二分搜索会给你一个任意元素；您必须搜索两种方式才能获得您正在寻找的范围。
- 在 C++ 中，您可以使用
equal_range方法在一次调用中产生您想要的结果。
为了加快在 Java 和 .NET 中搜索相等范围太长而无法进行线性迭代的情况，您可以查找前导元素和后继元素，并在您找到的范围中间取值，不包括结束。
如果由于第二次二分搜索而太慢，请考虑编写自己的搜索，同时查找两端。这可能有点乏味，但它应该运行得更快。
于 2012-08-27T15:26:26.907 回答
2
Java 中的这段代码在 O(logN) 时间内计算目标值在一次 pass中排序数组中的出现次数。很容易修改它以返回找到的索引列表，只需传入 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);
}
}
于 2020-12-15T20:20:11.550 回答
1
您的二进制搜索是否返回元素或元素所在的索引？你能得到索引吗？
由于列表已排序，所有匹配的元素都应该相邻出现。如果您可以获取标准搜索中返回的项目的索引，则只需从该索引开始双向搜索，直到找到不匹配项。
于 2012-08-27T15:24:37.813 回答
0
您可以使用以下代码解决您的问题。这里的主要目的是首先找到密钥的下限，然后找到相同的上限。后来我们得到了指数的差异，我们得到了答案。我们可以使用一个标志来查找同一函数的上限和下限，而不是使用两个不同的函数。
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int bin_search(int a[], int low, int high, int key, bool flag){
long long int mid,result=-1;
while(low<=high){
mid = (low+high)/2;
if(a[mid]<key)
low = mid + 1;
else if(a[mid]>key)
high = mid - 1;
else{
result = mid;
if(flag)
high=mid-1;//Go on searching towards left (lower indices)
else
low=mid+1;//Go on searching towards right (higher indices)
}
}
return result;
}
int main() {
int n,k,ctr,lowind,highind;
cin>>n>>k;
//k being the required number to find for
int a[n];
for(i=0;i<n;i++){
cin>>a[i];
}
sort(a,a+n);
lowind = bin_search(a,0,n-1,k,true);
if(lowind==-1)
ctr=0;
else{
highind = bin_search(a,0,n-1,k,false);
ctr= highind - lowind +1;
}
cout<<ctr<<endl;
return 0;
}
于 2019-01-30T05:44:23.327 回答
0
最近发现了非常有效的算法。
考虑到两个变量（输入大小和搜索键的数量），该算法具有对数时间复杂度。然而，搜索到的键也必须进行排序。
#define MIDDLE(left, right) ((left) + (((right) - (left)) >> 1))
int bs (const int *arr, int left, int right, int key, bool *found)
{
int middle = MIDDLE(left, right);
while (left <= right)
{
if (key < arr[middle])
right = middle - 1;
else if (key == arr[middle]) {
*found = true;
return middle;
}
else
left = middle + 1;
middle = MIDDLE(left, right);
}
*found = false;
/* left points to the position of first bigger element */
return left;
}
static void _mkbs (const int *arr, int arr_l, int arr_r,
const int *keys, int keys_l, int keys_r, int *results)
{
/* end condition */
if (keys_r - keys_l < 0)
return;
int keys_middle = MIDDLE(keys_l, keys_r);
/* throw away half of keys, if the key on keys_middle is out */
if (keys[keys_middle] < arr[arr_l]) {
_mkbs(arr, arr_l, arr_r, keys, keys_middle + 1, keys_r, results);
return;
}
if (keys[keys_middle] > arr[arr_r]) {
_mkbs(arr, arr_l, arr_r, keys, keys_l, keys_middle - 1, results);
return;
}
bool found;
int pos = bs(arr, arr_l, arr_r, keys[keys_middle], &found);
if (found)
results[keys_middle] = pos;
_mkbs(arr, arr_l, pos - 1, keys, keys_l, keys_middle - 1, results);
_mkbs(arr, (found) ? pos + 1 : pos, arr_r, keys, keys_middle + 1, keys_r, results);
}
void mkbs (const int *arr, int N, const int *keys, int M, int *results)
{ _mkbs(arr, 0, N - 1, keys, 0, M - 1, results); }
这是 C 中的实现和打算发表的论文草稿： https ://github.com/juliusmilan/multi_value_binary_search
你能分享一个用例吗？
于 2018-11-24T09:40:59.950 回答
0
尝试这个。它的效果惊人。
工作示例，点击这里
var arr = [1, 1, 2, 3, "a", "a", "a", "b", "c"]; // It should be sorted array.
// if it arr contain more than one keys than it will return an array indexes.
binarySearch(arr, "a", false);
function binarySearch(array, key, caseInsensitive) {
var keyArr = [];
var len = array.length;
var ub = (len - 1);
var p = 0;
var mid = 0;
var lb = p;
key = caseInsensitive && key && typeof key == "string" ? key.toLowerCase() : key;
function isCaseInsensitive(caseInsensitive, element) {
return caseInsensitive && element && typeof element == "string" ? element.toLowerCase() : element;
}
while (lb <= ub) {
mid = parseInt(lb + (ub - lb) / 2, 10);
if (key === isCaseInsensitive(caseInsensitive, array[mid])) {
keyArr.push(mid);
if (keyArr.length > len) {
return keyArr;
} else if (key == isCaseInsensitive(caseInsensitive, array[mid + 1])) {
for (var i = 1; i < len; i++) {
if (key != isCaseInsensitive(caseInsensitive, array[mid + i])) {
break;
} else {
keyArr.push(mid + i);
}
}
}
if (keyArr.length > len) {
return keyArr;
} else if (key == isCaseInsensitive(caseInsensitive, array[mid - 1])) {
for (var i = 1; i < len; i++) {
if (key != isCaseInsensitive(caseInsensitive, array[mid - i])) {
break;
} else {
keyArr.push(mid - i);
}
}
}
return keyArr;
} else if (key > isCaseInsensitive(caseInsensitive, array[mid])) {
lb = mid + 1;
} else {
ub = mid - 1;
}
}
return -1;
}
于 2017-03-27T22:47:36.033 回答
0
您可以进行两种搜索：一种用于范围之前的索引，另一种用于范围之后的索引。因为之前和之后可以重复 - 使用 float 作为“唯一”键”
static int[] findFromTo(int[] arr, int key) {
float beforeKey = (float) ((float) key - 0.2);
float afterKey = (float) ((float) key + 0.2);
int left = 0;
int right = arr.length - 1;
for (; left <= right;) {
int mid = left + (right - left) / 2;
float cur = (float) arr[mid];
if (beforeKey < cur)
right = mid - 1;
else
left = mid + 1;
}
leftAfter = 0;
right = arr.length - 1;
for (; leftAfter <= right;) {
int mid = left + (right - leftAfter) / 2;
float cur = (float) arr[mid];
if (afterKey < cur)
right = mid - 1;
else
left = mid + 1;
}
return new int[] { left, leftAfter };
}
于 2020-06-23T15:28:57.190 回答