Здравствуйте!
Есть задача на ulearn, называется "Левая граница". Суть - нужно реализовать метод (GetRightBorderIndex) рекурсивного бинарного поиска наибольшего слова в списке слов, которое было бы меньше prefix и не начиналось с prefix. Если такого нет - вернуть -1. На моём ПК всё отрабатывает корректно, на сайте выдаёт вот такую ошибку:
Exception on: Prefix [zzz], phrases [a, ab, abc]
Index was outside the bounds of the array.
В этом случае поиск по логике должен вернуть 2, он и возвращает. 3й день уже бьюсь, думаю может ошибка в тесте самом. Собственно, код:
using System;
using System.Collections.Generic;
using System.Linq;
namespace Autocomplete
{
// Внимание!
// Есть одна распространенная ловушка при сравнении строк: строки можно сравнивать по-разному:
// с учетом регистра, без учета, зависеть от кодировки и т.п.
// В файле словаря все слова отсортированы методом StringComparison.OrdinalIgnoreCase.
// Во всех функциях сравнения строк в C# можно передать способ сравнения.
public class LeftBorderTask
{
/// <returns>
/// Возвращает индекс левой границы.
/// То есть индекс максимальной фразы, которая не начинается с prefix и меньшая prefix.
/// Если такой нет, то возвращает -1
/// </returns>
/// <remarks>
/// Функция должна быть рекурсивной
/// и работать за O(log(items.Length)*L), где L — ограничение сверху на длину фразы
/// </remarks>
public static int GetLeftBorderIndex(IReadOnlyList<string> phrases, string prefix, int left, int right)
{
if (left == right)
{
if(phrases[left].StartsWith(prefix, StringComparison.OrdinalIgnoreCase)){
return left - 1;
}
if(string.Compare(phrases[left], prefix, StringComparison.OrdinalIgnoreCase) < 0){
return left;
}
return -1;
}
int middle = left + (right - left) / 2;
if (string.Compare(prefix, phrases[middle], StringComparison.OrdinalIgnoreCase) <= 0)
return GetLeftBorderIndex(phrases, prefix, left, middle);
return GetLeftBorderIndex(phrases, prefix, middle + 1, right);
}
}
}
Буду признателен за ответ.
