Расширение алгоритма двоичного поиска для поиска первого и последнего индекса ключевого значения, подлежащего поиску в массиве
-
19-09-2019 - |
Вопрос
Проблема состоит в том, чтобы расширить алгоритм двоичного поиска, чтобы наиболее эффективным способом находить все вхождения целевого значения в отсортированном массиве.Конкретно говоря, входными данными алгоритма являются (1) отсортированный массив целых чисел, где некоторые числа могут появляться более одного раза, и (2) целевое целое число для поиска.Результатом работы алгоритма должна быть пара значений индекса, указывающих на первое и последнее вхождение целого числа в массив, если оно действительно встречается.Исходный код может быть на c #, c, c ++.
Кроме того, каково максимальное и минимальное количество сравнений, которые нам могут понадобиться для поиска индексов?
Решение
Если вы немного поумнели, вы можете определить две разные функции бинарного поиска.Один вернет индекс первого появления искомого значения, а другой вернет последнее появление искомого значения.Исходя из ваших знаний о бинарном поиске, вы должны быть в состоянии определить максимальное и минимальное количество сравнений.
Использование двух двоичных поисковых запросов, на мой взгляд, должно быть самым быстрым методом в среднем.Например, если вы используете только один двоичный поиск, чтобы найти первый элемент, а затем выполняете линейный поиск, в худшем случае вся функция будет иметь одно и то же значение.Для массива длиной 10000 это дало бы 10013 сравнений в наихудшем случае, в то время как использование двух двоичных поисковых запросов дало бы 28 сравнений в наихудшем случае для одного и того же массива.Конечно, при использовании массива одинакового размера наилучшим вариантом для метода двоичного / линейного поиска было бы 14 сравнений, в то время как лучшим вариантом для метода двух двоичных поисков является 26 сравнений.
** Обновление
Итак, вот бинарный поиск для поиска первого появления элемента в массиве.Я дам вам рекурсивную функцию (вы, конечно, можете сделать ее итеративной и оптимизировать другими способами).При этом выполняется поиск значения int val в массиве a целых чисел.Кроме того, я не был осторожен с поиском средней точки (если массив действительно большой, могут возникнуть проблемы).
int bs1(int a[], int val, int left, int right)
{
if(right == left) return left;
int mid = (right+left)/2;
if(val > a[mid]) return bs1(a, val, mid+1, right);
else return bs1(a, val, left, mid);
}
Однако после того, как вам будет возвращен индекс, вы должны проверить, действительно ли он ссылается на правильное значение, потому что, если val отсутствует в массиве, возвращаемый индекс будет соответствовать следующему элементу, превышающему val.
Несколько незначительных изменений в этом приведут к появлению функции, которая находит последний элемент.Ключ к тому, чтобы сделать это, - правильно использовать компараторы и помнить, что целочисленное деление всегда усекается.
Другие советы
Для C ++ вы могли бы посмотреть std::equal_range()
и требования к его сложности.До тех пор, пока вас интересует базовый алгоритм, должны применяться одни и те же общие правила, независимо от языка, используемого для реализации.
Это довольно легко сделать без написания собственного алгоритма двоичного поиска, путем многократного вызова стандартного алгоритма.
// some curly-bracket language:
// int BinarySearch(sortedList, searchIndex, searchLength, valueToFind)
// returns the zero-based index of the item in the list, or a negative value
// if the item is not found
int inner = BinarySearch(list, 0, listSize, value);
if(inner < 0){
// handle case where value is not found in list
}
int bottom = inner, top = inner;
while(true){
int i = BinarySearch(list, 0, bottom, value);
if(i < 0)
break;
bottom = i;
}
while(true){
int i = BinarySearch(list, top + 1, listSize - top - 1, value);
if(i < 0)
break;
top = i;
}
// bottom and top now hold the bounds of all instances of value in list
Это довольно близко к той же эффективности, которую вы получили бы с помощью пользовательского алгоритма, за исключением того, что у вас больше накладных расходов на вызов функции.
Что касается количества сравнений, мне пришлось бы немного подумать, чтобы быть уверенным, но я думаю, что это всего лишь 2 * log2N, где N - количество элементов в списке.
Редактировать
Бах!Это не журнал 2 *2N, потому что в отличие от того, что вы могли бы сделать с помощью пользовательского алгоритма, он не исключает части списка постепенно.Это кажется1 что максимальное количество сравнений равно (log2N - 0,5) * логарифм2N.Это все еще только 885 сравнений для списка с 230 элементы (390 сравнений для 220 N, и 95 для 210 N), но мы можем сделать лучше, чем это.
// int Compare(a, b)
// returns 0 if a and b are equal,
// a negative value if a < b, or
// a positive value if a > b
int start = 0, end = listSize, inner;
while(true){
if(end == start){
// handle case where value is not found in list
}
inner = (start + end) / 2;
int cmp = Compare(list[inner], value);
if(cmp == 0)
break;
if(cmp < 0)
start = inner + 1;
else end = inner;
}
int top = inner, bottom = inner;
while(true){
if(start >= bottom)
break;
inner = (start + bottom) / 2;
int cmp = Compare(list[inner], value);
if(cmp == 0)
bottom = inner;
else start = inner + 1;
}
while(true){
if(end - 1 <= top)
break;
inner = (top + 1 + end) / 2;
int cmp = Compare(list[inner], value);
if(cmp == 0)
top = inner;
else end = inner;
}
Это займет не более 2 * log2N сравнений.230 элементы потребуют не более 60 сравнений, 220 элементы потребуют не более 40 сравнений и т.д.
1 Я определил это экспериментально.Я не настолько умен, чтобы вычислить это математически.
Вы можете найти обсуждение этого вопроса в Bentley Жемчужины программирования и Том 3 книги Кнута. :Сортировка и поиск.
Вот одна реализация на C ++ : http://the-algo-blog.blogspot.com/2011/06/binary-search-to-find-last-and-first.html
Нет четкого ответа на самую эффективную часть вопроса.Это будет зависеть от того, сколько записей с одинаковым значением следует ожидать.Если их несколько, линейный поиск в обоих направлениях массива после нахождения одного элемента будет для вас самым быстрым вариантом, но если вы ожидаете много записей с одинаковым значением, вы могли бы выполнить своего рода бинарный поиск, чтобы найти начальные конечные индексы.
Отказ от ответственности:Не проверено;он предназначен для демонстрации идеи, а не для непосредственного использования в качестве производственного кода
int org = binarySearch(array,value) //do the binary search and find on element
int min = org-delta; //delta is some constant based on how many elemts are to be expected
int max = org;
min = min < 0 ? 0 : min;
int search= min;
bool latestWasHit = false;
while(search > 0)
{
if(search+1 == max)
return max;
if(array[search] != value)
{
min = search;
search = search + (max-search)/2
}
else
{
max = search;
search = (search-min)/2;
}
}
а затем обратное для верхней границы.Однако потребуется довольно много элементов, прежде чем это будет быстрее, чем простой линейный поиск.
Я предполагаю, что в обычном алгоритме было бы что-то вроде этого:
if(value == test) return;
if(value < test) min = i;
if(value > test) max = i;
После того как вы использовали это для поиска одного из значений, выполните еще два слегка измененных двоичных поиска, используя min и max, которые вам в данный момент нужны для поиска подсказок.
Чтобы найти самый лучший вариант, замените приведенный выше на:
if(value <= test) min = i;
if(value > test) max = i;
для самого нижнего замените на:
if(value >= test) max = i;
if(value < test) min = i;
Обратите внимание, что при использовании этого метода нет раннего возврата, вы просто продолжаете, пока min и max не станут похожи на одно или что-то другое, я полагаю, вы могли бы добавить одно с другой проверкой
if(value == test and arr[i-1] != test) return;
и т.д.
Я создал два метода бинарного поиска для возврата первого и последнего вхождений соответственно.
public static void main(String[] args) {
int a[] ={1,2,2,2,2,2,5,5,6,8,9,10};
System.out.println(5+" first = "+first(a, 5, 0, a.length-1));
System.out.println(5+" last = "+right(a, 5, 0, a.length-1));
System.out.println(1+" first = "+first(a, 1, 0, a.length-1));
System.out.println(1+" last = "+right(a, 1, 0, a.length-1));
System.out.println(2+" first = "+first(a, 2, 0, a.length-1));
System.out.println(2+" last = "+right(a, 2, 0, a.length-1));
System.out.println(10+" first = "+first(a, 10, 0, a.length-1));
System.out.println(10+" last = "+right(a, 10, 0, a.length-1));
System.out.println(8+" first = "+first(a, 8, 0, a.length-1));
System.out.println(8+" last = "+right(a, 8, 0, a.length-1));
System.out.println(11+" first = "+first(a, 11, 0, a.length-1));
System.out.println(11+" last = "+right(a, 11, 0, a.length-1));
}
private static int first(int [] a, int x, int l, int h){
if(l>h){
return -1;
}
int mid = (h-l)/2+l;
if(a[mid] == x && (mid==0 || a[mid-1] != x) ){
return mid;
}else if(a[mid] == x){
return first(a, x, l, mid-1);
}else if(a[mid]>x){
return first(a, x, l, mid-1);
}else{
return first(a, x, mid+1, h);
}
}
private static int right(int [] a, int x, int l, int h){
if(l>h){
return -1;
}
int mid = (h-l)/2+l;
if(a[mid] == x && (mid==a.length-1 || a[mid+1] != x) ){
return mid;
}else if(a[mid] == x){
return right(a, x, mid+1, h);
}else if(a[mid]>x){
return right(a, x, l, mid-1);
}else{
return right(a, x, mid+1, h);
}
}
Output:
1 first = 0
1 last = 0
2 first = 1
2 last = 5
10 first = 11
10 last = 11
8 first = 9
8 last = 9
11 first = -1
11 last = -1