1

Думал всегда, что это какой то сложный алгоритм, но посмотрев понял, что фигня. Но сказали, что реализовать я его не смогу. Решил попробовать и за пару ночных часиков получил удачный алгоритм.

Подсказок пока не хочу, есть лишь один вопрос, ответ на который я в явном виде не нахожу (опять же не хочу случайно прочитать подсказки).

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

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

 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;
8
  • вообще лучше знать.
    – pavel
    31 мая 2018 в 19:44
  • 1
    Проверить два числа (два рядом могут оказаться одинаковыми!), по ним определить возрастание/убывание. По результату применить алгоритм. Логика одинакова, только менять направление. 31 мая 2018 в 19:48
  • да, логика одинакова, но кода в два раза больше ) отдельный кусок кода на обратное направление. И еще один алгоритм для определения возр. или убыв.
    – Turalllb
    31 мая 2018 в 20:01
  • Да, строки добавляются (проверка флага направления), но не в два раза больше А чтобы быстро, без проверок - два почти одинаковых кода 31 мая 2018 в 20:10
  • ну ясно, я просто думал, вдруг я что нибудь не учел и есть универсальный алгоритм, которому не важно возр. массив или убывающий. Если немного подумать, то становится очевидным, что такое невозможно.
    – Turalllb
    31 мая 2018 в 20:12

1 ответ 1

2

Требования весьма простые:

  1. Должен существовать алгоритм поиска среднего элемента, находящегося между двумя заданными элементами, за константное время
  2. Массив должен предоставлять доступ к элементу с заданным индексом за константное время
  3. Для всех элементов в рассматриваемом диапазоне массива должна быть определена функция порядка F(x), причем
    • F(xi) ≤ F(xj) для любых i < j
    • Если F(xi) = F(xj), то это равносильно утверждению xi = xj
4
  • Какие то странные требования ... и каким же образом методом разделяй и властвуй можно получить константное время и при массиве из 100 элементов и в массиве из 10 000 000 элементов? Да никак
    – Turalllb
    31 мая 2018 в 20:09
  • ааа...не так прочитал. Должен по индексу выдавать элемент, а не по элементу индекс. Ну это "обычный" массив.
    – Turalllb
    31 мая 2018 в 20:14
  • @TuralllbТо, что вы называете "обычным массивом" может быть реализацией связанного списка. Например, объект класса LinkedList в Java предоставляет доступ к элементу с произвольным индексом, но делает это за линейное время 31 мая 2018 в 20:20
  • нет, связный список я не называю обычным массивом ) обычный массив это обычный )) , где в одном выделенном участке памяти последовательно лежат элементы )
    – Turalllb
    31 мая 2018 в 20:23

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.