@LuVairo

Как исправить алгоритм бинарного поиска правой границы?

Помогите, пожалуйста, исправить алгоритм бинарного поиска правой границы. Мой вариант не проходит тесты.
Важно: в метод изначально передаются след. параметры: left = -1, right = phrases.Count
Правая граница - индекс первого элемента большего заданного или N, если такого нет.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Threading;

namespace Autocomplete
{
    public class RightBorderTask
    {
        /// <returns>
        /// Возвращает индекс правой границы. 
        /// То есть индекс минимального элемента, который не начинается с prefix и большего prefix.
        /// Если такого нет, то возвращает phrases.Count
        /// </returns>
        /// <remarks>
        /// Функция должна быть НЕ рекурсивной
        /// и работать за O(log(items.Length)*L), где L — ограничение сверху на длину фразы
        /// </remarks>
        public static int GetRightBorderIndex(IReadOnlyList<string> phrases, string prefix, int left, int right)
        {
            if (phrases.Count == 0)
                return 0;

            while (left < right)
            {
                if (left + 1 >= right || phrases[left + 1].CompareTo(prefix) >= 0)
                    return left + 1;

                var middle = (left + right) / 2;

                if (phrases[middle].StartsWith(prefix) || phrases[middle].CompareTo(prefix) <= 0)
                    left = middle + 1;
                else
                    right = middle;
            }

            return left + 1;
        }
    }
}
  • Вопрос задан
  • 304 просмотра
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Если в метод передаются
left = -1, right = phrases.Count
, то их физический смысл: left - последний элемент точно левее искомой позиции (строка там или меньше pref, или начинается с него), а right - последний элемент точно правее искомой позиции (строка там больше pref и не начинается с него).

Это не совсем стандартный инвариант. Обычно считают, что left, это такая позиция, что ответ не может быть левее ее, а right, что ответ не может быть правее.

Но можно и с вашим инвариантом работать. Вам надо соответсвтующим образом менять left и right, чтобы инвариант поддерживался.

Во-первых, если left == right -2, то вы уже знаете ответ - это может быть только left+1. Эти и должно быть условие в while. Правда стоит эту позицию после цикла все-таки проверить. Вдруг все строки в массиве меньше pref.

Далее, подсчитали вы mid, если строка там оказалась меньше pref или c него начинается, то left = mid. Ведь уже следующая позиция может оказаться искомой, а физический смысл left, напоминаю - "точно левее искомой позиции". В противном случае надо делать right = mid+1. Ведь позиция mid вполне может и быть ответом.

Вопрос, а не зациклится ли такой алгоритм? right-left >= 3. Значит mid оказывается строго больше left. Также, поскольку у вас округление вниз, то mid < right-1, а занчит в любом случае либо left либо right сдвинутся так, что длина отрезка уменьшится. Алгоритм не циклится.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы