Расширение алгоритма двоичного поиска для поиска первого и последнего индексов значения ключа для поиска в массиве

Если вы немного сообразительны, вы можете определить две разные функции двоичного поиска. Один вернет индекс первого появления искомого значения, а другой вернет последнее появление искомого значения. Исходя из ваших знаний о двоичном поиске, вы сможете определить максимальное и минимальное количество сравнений.

На мой взгляд, использование двух бинарных поисковых запросов должно быть в среднем самым быстрым методом. Например, если вы используете только один двоичный поиск, чтобы найти первый элемент, а затем выполняете линейный поиск, худшим случаем будет, если вся функция будет иметь одно и то же значение. Для массива длиной 10000 это дало бы 10013 сравнений в худшем случае, тогда как использование двух бинарных поисков дало бы 28 сравнений в худшем случае для одного и того же массива. Конечно, при использовании того же размера массива наилучшим случаем для метода двоичного / линейного поиска будет 14 сравнений, в то время как наилучшим случаем для метода двух двоичных поисков будет 26 сравнений.

** Обновлять

Хорошо, вот двоичный поиск, чтобы найти первое появление элемента в массиве. Я дам вам рекурсивную функцию (вы, конечно, можете сделать ее итеративной и оптимизировать другими способами). Это ищет int val в массиве a int. Кроме того, я не был внимателен к поиску средней точки (если массив действительно большой, могут возникнуть проблемы).

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 * log ₂ N, где N - количество элементов в списке.

Изменить

Ба! Это не 2 * log ₂ N, потому что в отличие от того, что вы могли бы сделать с помощью специального алгоритма, он не исключает постепенно части списка. Кажется ¹, что максимальное количество сравнений составляет (log ₂ N - 0,5) * log ₂ N. Это все еще всего 885 сравнений для списка с 2 ³⁰ элементами (390 сравнений для 2 ²⁰ N и 95 для 2 ¹⁰ 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 * log ₂ N сравнений. Для 2 ³⁰ элементов потребуется не более 60 сравнений, для 2 ²⁰ элементов потребуется не более 40 сравнений и т. Д.

_{¹ Я определил это экспериментально. Я недостаточно умен, чтобы понять это математически.}

Вы можете найти обсуждение этого в Bentley Programming Pearls и Knuth's Vol.3: Sorting and Searching.

Вот одна реализация на 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