Бинарный поиск сравнить со строковыми объектами

Question

class ObjectBinarySearcher{

    public static int search(String[] array, String value){

        int first = 0, last = array.length-1, position = -1;
        boolean found = false;

        while(!found && first < last){
            int mid = (first+last)/2;
            int midValue = array[mid].compareTo(value);

            if(midValue==0){
                position = mid;
                found = true;
            }
            else if(midValue<0)
                last = mid-1;
            else
                first = mid+1;
        }

        return position;
    }
}

Я отправляю массив, содержащий {"love", "hate", "happy", "sad", "нейтральный"}, и каждый раз, когда я пытаюсь использовать мой метод двоичного поиска для поиска "нейтрального", он говорит мне это не найдено. Что является причиной этого?

Answer 1

1. Ваш входной массив должен быть отсортирован, чтобы использовать бинарный поиск.

2. Как указал @Libby, ваш цикл while должен измениться так, чтобы первый был меньше или равен последнему.

3. Вы должны иметь возможность выйти из цикла, если не найдено совпадений, когда first == last,

4. Если midValue < 0, вам нужно переместить нижнюю границу, а не верхнюю границу (и наоборот).

Новый код:

while (!found && first <= last) { // allow first to be lower or equal to last
    int mid = (first + last) / 2;
    int midValue = array[mid].compareTo(value);

    if (midValue == 0) { // matched!

        position = mid;
        found = true;

    } else if (first == last) { // didn't match and there was only one left to check

        break; // so break out of the loop

    } else if (midValue < 0) { // current pos is too low

        first = mid + 1; // so adjust the lower bound

    } else { // current pos is too high

        last = mid - 1; // so adjust the upper bound

    }
}

Answer 2

Изменить while loop в while(!found && first <= last)