Я использую стандартный двоичный поиск, чтобы быстро вернуть один объект в отсортированный список (по отношению к сортируемому свойству).
Теперь мне нужно изменить поиск, чтобы возвращались ВСЕ записи списка совпадений. Как мне лучше всего это сделать?
Ну, поскольку список отсортирован, все записи, которые вас интересуют, смежны. Это означает, что вам нужно найти первый элемент, равный найденному элементу, оглядываясь назад от индекса, который был создан двоичным поиском. И то же самое касается последнего элемента.
Вы можете просто вернуться назад от найденного индекса, но таким образом решение может быть таким же медленным, как и 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);
}
Цитата из проф.Скиена: Предположим, мы удалим тест равенства, если (s [средний] == ключ) возвращение (средний); от реализации выше и вернуть индекс низкий вместо -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);
}
Надеюсь, что это полезно:)
Если я следую вашему вопросу, у вас есть список объектов, которые для целей сравнения выглядят как {1,2,2,3,4,5,5,5,6,7,8,8,9}. Обычный поиск по 5 ударит по одному из объектов, которые сравниваются как 5, но вы хотите получить их все, верно?
В этом случае я предлагаю стандартный двоичный поиск, который после приземления на соответствующем элементе начинает смотреть влево до тех пор, пока он не перестанет соответствовать, а затем вправо (от первого совпадения) снова, пока он не перестанет соответствовать.
Будьте осторожны, что любая структура данных, которую вы используете, не переписывает элементы, которые сравниваются с тем же!
В качестве альтернативы рассмотрите возможность использования структуры, в которой хранятся элементы, которые сравниваются с ведром в этой позиции.
Я бы выполнил два бинарных поиска: один ищет первый элемент, сравнивающий >= значение (в терминах С++, lower_bound), а затем один ищет первый элемент, сравнивающий > значение (в терминах С++, upper_bound). Элементы from lower_bound только перед верхней границей - это то, что вы ищете (в терминах java.util.SortedSet, подмножество (ключ, ключ)).
Итак, вам нужно две разные небольшие модификации стандартного бинарного поиска: вы все еще проверяете и используете сравнение в зонде, чтобы сузить область, в которой значение, которое вы ищете, должно лежать, но теперь, например, для lower_bound, если вы достигли равенства, все, что вы знаете, - это то, что элемент, который вы ищете (первое равное значение), находится где-то между первым элементом диапазона и значением, которое вы только что проверили, - вы не можете сразу вернуться.
Как только вы нашли совпадение с 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);
}
Никакие угловые случаи не покрыты. Я думаю, что это удержит сложность ur (O (logN)).
Это зависит от того, какую реализацию бинарного поиска вы используете:
equal_range для получения результата, который вы хотите в одном вызове.Чтобы ускорить поиск в Java и .NET для случаев, когда равный диапазон слишком длинный для линейного итерации, вы можете искать элемент-предшественник и элемент-преемник и принимать значения в середине диапазона, который вы найдете, за исключением концов.
Если это будет слишком медленным из-за второго бинарного поиска, подумайте о том, чтобы написать собственный поиск, который ищет оба конца в одно и то же время. Это может быть немного утомительно, но он должен работать быстрее.
Я бы начал с поиска индекса одного элемента с учетом сортируемого свойства (используя "обычный" двоичный поиск), а затем начните искать как левое, так и правое из элемента в списке, добавив все найденные элементы удовлетворяют критерию поиска, останавливаясь на одном конце, когда элемент не соответствует критерию, или больше нет элементов для перемещения, и вообще останавливается, когда оба конца слева и справа удовлетворяют упомянутым ранее условиям остановки.
возвращает ли ваш бинарный поиск элемент или индекс, на котором находится элемент? Вы можете получить индекс?
Поскольку список сортируется, все соответствующие элементы должны отображаться рядом. Если вы можете получить индекс элемента, возвращаемого в стандартном поиске, вам просто нужно искать в обоих направлениях от этого индекса до тех пор, пока не найдете несоответствия.
Попробуйте это. Он работает удивительно.
рабочий пример, Нажмите здесь
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;
}
Вы можете использовать приведенный ниже код для вашей проблемы. Основная цель здесь - сначала найти нижнюю границу ключа, а затем найти верхнюю границу ключа. Позже мы получаем разницу показателей и получаем наш ответ. Вместо того, чтобы иметь две разные функции, мы можем использовать флаг, который можно использовать для поиска верхней и нижней границ в одной и той же функции.
#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;
}
class binary_search_descending_multiple_s
{
public static void main(int s)
{
int a[]={100,100,100,100,100,100,100,100,99,100,87,80,90,78,87,8,64,100,99,99,99,99,99,99};
int l=a.length;
int i,x,c,fv=0,lv=l-1,m;
for(i=0;i<l-1;i++)
{
for(x=i+1;x<l;x++)
{
if(a[i]<a[x])//descending order used
{
c=a[i];
a[i]=a[x];
a[x]=c;
}
}
}
c=0;
while(fv<=lv&&c==0)
{
m=(lv+fv)/2;
if(a[m]==s)
{
System.out.println("found at"+(m+1));
int xr=m+1;//for right side nos
int xl=m-1;//for left side nos
c=0;
while(c>=-1 && xr<a.length)
{
if(a[xr]==s)
System.out.println("found at"+(xr+1));
else//to terminate the loop
break;
xr++;//increment to check terms further right
}
while(c>=0 && xl>=0)//for left side
{
if(a[xl]==s)
System.out.println("found at"+(xl+1));
else//to terminate the loop
break;
xl-=1;//decrement to check terms further left
}
c=1;
}
if(a[m]<=s)
lv=m-1;
if(a[m]>s)
fv=m+1;
}
}
}
Эта программа будет сортировать данные в порядке убывания, а затем искать. Он работает с одиночными прыжками, хотя двойные прыжки могут привести к пропуску значения. Прочитайте программу, и вы поймете.
Очень эффективный алгоритм для этого был найден недавно.
Алгоритм имеет логарифмическую временную сложность, учитывая обе переменные (размер ввода и количество искомых ключей). Однако искомые ключи также должны быть отсортированы.
#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
Можете ли вы поделиться примером использования?