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

Question

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

//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); 
} 

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

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

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

тесты Строка ввода = abcdefghijklmnopqrstuvwxyzaeiou Возвращения из Подсписка метода:
фрагмент 1 (используется 4 из 10): [ч] [ я] [I] [J]
фрагмент 2 (используется 4 из 10): [K] [L] [м] [п]

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

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

Answer 1

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

Ваш текущий подход вводит излишнюю сложность и потенциально изменяет алгоритм 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 2

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

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

Answer 3

Проверить official description из CompareTo (String) метод

Из док:

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

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

вашего время однопетлевым

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

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

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