почему CompareTo возвращает true, когда оно должно быть false?

Question

Я отлаживаю ошибочные результаты поиска из моего проекта класса структур данных. Этот текущий проект потребовал от нас создать упорядоченный развернутый связанный список и выполнить поиск по содержимому, а затем вернуть подсписок элементов из включающей начальной точки в эксклюзивную конечную точку. Чтобы сделать это, я должен искать во внутреннем массиве, чтобы найти точку индекса начального элемента. Я делаю это с помощью бинарного поиска, но так как он возвращает только первое найденное совпадение, и перед ним могут быть другие совпадения, мне нужно вернуться в массив, чтобы найти первое истинное совпадение. Я делаю это через

//get first index match, work backwards
int index= binarySearch(node.items, 0, node.numUsed, item, comp);
while (index>0 && comp.compare(node.items[index], item)==0){
    index--;
}

Профессор предоставил тестовый код, который разбивает строку и добавляет каждый символ как элемент в структуре. Он также включил вложенный класс StringCmp, на который ссылается как comp в объявлении бинарного поиска выше. Его метод сравнения -

public int compare(String s1, String s2) {
  cmpCnt++;
  return s1.compareTo(s2);
}

Однако при запуске теста метода sublist от i до o этот метод возвращает истинное значение, когда comp.compare(h,i)==0, и это отбрасывает мои результаты запуска из класса поиска, который я написал. Первоначально я компенсировал return index++, чего было достаточно, чтобы пройти испытание конструкции, но отбросил ожидаемую начальную точку на единицу.

Так почему же это возвращение истинно, когда оно явно ложно?

РЕДАКТИРОВАТЬ добавлена ​​распечатка метода подсписка, который будет работать от i до o

Входная тестовая строка = abcdefghijklmnopqrstuvwxyzaeiou Возврат из метода подсписка:
кусок 1 (используется 4 из 10): [h] [i] [i] [j]
кусок 2 (используется 4 из 10): [k] [l] [m] [n]

h вообще не должно быть в списке, но comp.compare(node.items[index], item)==0 возвращает true, что i == h, что, очевидно, неверно.

Редактировать два Вторая часть проекта требует, чтобы мы проанализировали текстовый файл, построили объекты Song из полей Artist, Title и Lyrics, а затем запустили поиск по заголовкам, используя префикс. Ошибка, возникающая здесь, не возникает при поиске по одной или нескольким буквам, поэтому я думаю, что проблема заключается во вложенном классе StringCmp в тесте.

Answer 1

Знаете ли вы, что compare() должно вернуть?Обычно такие функции возвращают отрицательное значение, если первый аргумент меньше второго, 0, если они равны, и положительное значение, если первый аргумент больше второго.

Кроме того, что выполняетсортировать по вашему массиву?Не могли бы вы опубликовать свой код binarySearch(), чтобы мы могли увидеть, в чем проблема?

Answer 2

ваш цикл while

while (index>0 && comp.compare(node.items[index], item)==0){
    index--;
}

превышает первое совпадение на единицу, поскольку вы уменьшаете индекс для каждого совпадения, оставляя вас с индексом, который больше не совпадает.Вызов Компаратора для элемента с индексом 1 вместо этого исправит это:

while (index>0 && comp.compare(node.items[index-1], item)==0){
    index--;
}

Answer 3

Поскольку вы реализовали свой собственный двоичный поиск, вы должны продолжать использовать его для поиска первого соответствующего элемента в массиве, а не останавливаться, как только найдете совпадение.

Ваш текущий подход вносит ненужную сложность и потенциально меняет алгоритм O (log N) на алгоритм O (N), если ваш входной массив состоит из всех идентичных значений.

Я полагаю, ваш текущий алгоритм выглядит примерно так:

int low = 0; 
int high = a.length-1;
while (low <= high) {
    int mid = (low + high) / 2;
    int cmp = comp.compare(a[mid], key);
    if (cmp < 0)
        low = mid + 1;
    else if (cmp > 0)
        high = mid - 1;
    else
        return mid;
}
return -1;

замена этого кода ниже должна сработать

int low = 0;
int high = a.length-1;
while (low < high) {
    int mid = (low + high) / 2;
    int cmp = comp.compare(a[mid], key);
    if (cmp < 0)
        low = mid + 1;
    else
        high = mid;
}
if (comp.compare(a[low], key) == 0)
    return low;
else 
    return -1;

Answer 4

Из любопытства, разве это не будет более подходящим для того, что вы пытаетесь сделать?

//get first index match, work backwards
int index= binarySearch(node.items, 0, node.numUsed, item, comp);

for (int i = index; i >= 0; i--) {
    if (comp.compare(node.items[index], item)==0))
        index = i;
}

Answer 5

Проверка официальное описание метода сравнения (String)

Из документа:

Возвращает: значение 0, если строка аргумента равна этой строке; значение меньше 0, если эта строка лексикографически меньше строкового аргумента; и значение больше 0, если эта строка лексикографически больше строкового аргумента.