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

Question

[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;
        }
    }
}

Comments

[Akina]

Эммм... функция учитывает, что в массиве могут быть равные элементы?

[Wataru]

В чем физический смысл left и right? Какой инвариант вы поддерживаете?

[mayton2019]

Автор а можешь написать что должно возвращаться в таких вот примерах? Хотя-бы несколько штук.

GetRightBorderIndex(List("abr","abra","cadabra","abraca"), "abra", -1, 4)

[LuVairo]

mayton2019, 2

[LuVairo]

Wataru, это как "ограничители" слева и справа при бинарном поиске

[LuVairo]

mayton2019, элементы сравниваются лексикографически

Answer 1

[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 сдвинутся так, что длина отрезка уменьшится. Алгоритм не циклится.

Comments

[LuVairo]

Спасибо, попробую)

[Василий Банников]

LuVairo, если поможет - отметьте решением

[LuVairo]

Wataru, в итоге должен получиться такой код, как я понимаю.
Выдаёт след. ошибку:
Error on: Prefix [abc], phrases [a, ab, abc]
result should be 3, but was 2

using System;
using System.Collections.Generic;
using System.Linq;
using System.Threading;

namespace Autocomplete
{
    public class RightBorderTask
    {
        public static int GetRightBorderIndex(IReadOnlyList<string> phrases, string prefix, int left, int right)
        {
            if (phrases.Count == 0)
                return 0;

            while (left < right)
            {
                if (left == right - 2)
                    return left + 1;

                var middle = (left + right) / 2;

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

            return left;
        }
    }
}

[Wataru]

LuVairo,

Во-первых, у вас цикл неверный. надо left < right-2. Вы внимательно прочитали мой ответ?
Во-вторых, в конце проверяйте, а что там за элемент в left+1. Если он меньше prefix или начинается с него, то надо выдавать phrases.Count.

[LuVairo]

Wataru, исправил, как вы сказали. Теперь всё работает! Большое спасибо!)

[d'Ivan]

LuVairo,

LuVairo, если поможет - отметьте решением