Думал всегда, что это какой то сложный алгоритм, но посмотрев понял, что фигня. Но сказали, что реализовать я его не смогу. Решил попробовать и за пару ночных часиков получил удачный алгоритм.
Подсказок пока не хочу, есть лишь один вопрос, ответ на который я в явном виде не нахожу (опять же не хочу случайно прочитать подсказки).
Скажите какие условия к массиву, чтобы можно было выполнять бинарный поиск. Упорядоченность это раз. А возрастающий или убывающий он мы должны знать?
Знаю, что можно проверить какой он и в зависимости от этого выбирать тот или иной алгоритм. Но если окажется, что алгоритм должен быть универсален и для убывающего и для возрастающего, то моя реализация похоже не канает.
Остается только добавить условие и если массив убывающий использовать обратный алгоритм.
Integer binarySearch(int value) {
middle = array.length / 2;
lastElement = array.length;
firstElement = 0;
while (array[middle] != value) {
if (array[middle] < value) {
firstElement = middle;
middle = (middle + lastElement) / 2;
if (middle == firstElement) return null;
} else {
lastElement = middle;
middle = (firstElement + lastElement) / 2;
if (middle == lastElement) return null;
}
}
return middle;
}
UPD Нашел две ошибки в своей реализации бинарного поиска. Искал ошибку, которая была в JDK 20 лет, но сперва нашел, что массив без элементов свалит мой код. Поэтому надо добавить, вот такую проверку : if(array.length == 0) return null;
Чуть позже нашел вторую ошибку, которая была в JDK, не находил её потому, что не рассматривал ситуацию, что может прийти число не int диапазона. Да, не int диапазон не придет, но он может появиться далее в строке middle = (firstElement + lastElement) / 2;
Поэтому переписал её так middle = firstElement/2 + lastElement/2
Но потом решил, что операция деления более затратная, чем вычитания или сложения и написал вот так
middle = (lastElement - firstElement)/2 + firstElement;