Изучите основы бинарного поиска
Бинарный поиск — это алгоритм, который используется для поиска элемента в отсортированном массиве. Этот алгоритм сравнивает целевое значение со средним элементом массива. Если значения не равны, а целевое значение меньше среднего значения, то большая половина исключается, или если целевое значение больше среднего значения, то удаляется меньшая половина. Таким образом, после каждого сравнения массив уменьшается вдвое. Этот процесс повторяется до тех пор, пока мы не найдем целевое значение или не найдем целевое значение.
Поиск — одно из фундаментальных понятий информатики. Итак, важно знать, как работает поиск. Есть много способов поиска, и бинарный поиск — один из них. Это эффективный способ найти целевое значение из отсортированного массива. В этом посте я реализую бинарный поиск и его варианты, чтобы решить несколько классных задач!
Временная сложность
Big-O или асимптотическая верхняя граница этого алгоритма равна 0(log n). Давайте пройдемся по математическому доказательству временной сложности.
Iteration 1 = n [if the length of the array is n]
Iteration 2 = n/2 [only half of the array needs to be checked]
Iteration 3 = (n/2) / 2 = (n/2) x (1/2) = (n/2^2)
Iteration q = (n/2^q) = 1 [after q iteration, n reduces to size 1]
=> n = 2^q
=> log2 (n) = log2 (2^q) [logb(x^y) = y logb(x)]
=> log2 (n) = q log2 (2) [logb(b) = 1]
=> log2 (n) = q
Таким образом, в худшем случае необходимо проверить q элементов. Например, если целевым значением является первый элемент или последний элемент, количество сравнений будет равно ceil(log2 (n)) или не будет представлено в списке. Но асимптотически ceil(log2 (n)) совпадает с log2 (n), поэтому оно будет вести себя как log2 (n), когда n станет очень большим. Более того, Big-Omega или асимптотическая нижняя граница этого алгоритма равна Ω(1), потому что в лучшем случае ему нужно проверить только 1 элемента. Например, когда целевое значение является средним элементом массива.
Бинарный поиск
Вот реализация JAVA двоичного поиска. Он вернет индекс целевого значения, если он будет найден. В противном случае он вернет -1.
Теперь я расскажу о четырех вариантах бинарного поиска. Используя эти четыре типа, вы можете решить следующие проблемы.
- Найти первое вхождение в массиве. Какова первая позиция заданного числа в массиве.
- Найти последнее вхождение в массиве. Какова последняя позиция заданного числа в массиве.
- Найти верхнюю границу в массиве. Какая самая высокая позиция вставки заданного числа будет поддерживать порядок сортировки в массиве,
- Найти нижнюю границу в массиве. Какая самая нижняя позиция вставки заданного числа будет поддерживать порядок сортировки в массиве.
Ниже я собираюсь решить эти проблемы с помощью JAVA, в котором используется концепция бинарного поиска.
Первое появление
Допустим, у нас есть следующий массив, и мы хотим найти первое вхождение 1. Тогда этот метод вернет 0;
int numbers [] = {1, 1, 1};
System.out.println(firstOccurrence(numbers, 1));
Как вы можете, мы немного изменили Бинарный поиск. Здесь у нас есть новая переменная с именем pos. Это потому, что мы не хотим возвращать индекс, как только найдем целевое значение. Вместо этого мы хотим обновить переменную pos и продолжить поиск в левой половине.
Последнее появление
Теперь предположим, что у нас есть следующий массив, и мы хотим найти последнее вхождение 1. Тогда этот метод вернет 2;
int numbers [] = {1, 1, 1};
System.out.println(lastOccurrence(numbers, 1));
Единственная разница с предыдущим методом в том, что мы хотим смотреть в правую половину.
Верхняя граница
Какова самая высокая возможная позиция вставки 11 в следующий массив, чтобы он сохранял порядок сортировки?
<- upper bound of 11 +---+---+---+---+----+----+----+----+----+----+----+ | 2 | 3 | 5 | 7 | 11 | 11 | 13 | 17 | 19 | 23 | 29 | +---+---+---+---+----+----+----+----+----+----+----+ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | +---+---+---+---+----+----+----+----+----+----+----+
Позиция будет 6, потому что это последний возможный индекс вставки, который будет поддерживать порядок сортировки. Здесь мы предположили, что если мы впишем 11 в номер индекса 6, то массив сдвинется вправо на один индекс.
Какова верхняя граница 10? Это 4, потому что мы не можем вставить 10 выше порядкового номера 4, потому что массив станет несортированным.
JAVA-реализация метода верхней границы.
Нижняя граница
Какова самая нижняя возможная позиция вставки 11 в следующий массив, чтобы он сохранял порядок сортировки?
lower bound of 11 -> +---+---+---+---+----+----+----+----+----+----+----+ | 2 | 3 | 5 | 7 | 11 | 11 | 13 | 17 | 19 | 23 | 29 | +---+---+---+---+----+----+----+----+----+----+----+ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | +---+---+---+---+----+----+----+----+----+----+----+
Позиция будет 4, потому что мы не можем вставить 11 в индекс с номером 3, потому что массив станет несортированным. Здесь мы предположили, что если мы впишем 11 в номер индекса 4, то массив сдвинется вправо на один индекс.
Какова нижняя граница 10? Это 4, потому что мы не можем вставить 10 ниже порядкового номера 4, потому что массив станет несортированным.
lower bound of 10 -><- upper bound of 10 +---+---+---+---+----+----+----+----+----+----+----+ | 2 | 3 | 5 | 7 | 11 | 11 | 13 | 17 | 19 | 23 | 29 | +---+---+---+---+----+----+----+----+----+----+----+ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | +---+---+---+---+----+----+----+----+----+----+----+
Из нашего наблюдения мы можем сказать, что верхняя и нижняя границы будут одинаковыми, если целевое значение не существует в массиве.
Реализация JAVA метода нижней границы.
Практические применения верхних и нижних границ
Существует множество приложений верхних и нижних границ. Здесь я покажу, как мы можем подсчитать частоту появления числа в массиве.
+---+---+---+---+----+----+----+----+----+----+----+ | 2 | 3 | 5 | 7 | 11 | 11 | 13 | 17 | 19 | 23 | 29 | +---+---+---+---+----+----+----+----+----+----+----+ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | +---+---+---+---+----+----+----+----+----+----+----+
Следующий метод вернет 2 для числа 11, поскольку в массиве два одиннадцати.
Обновление (19 мая 2021 г.)
Следующий расчет может привести к ошибке переполнения.
mid = (left + right) / 2;
Чтобы смягчить эту проблему, мы можем переписать приведенную выше строку, как показано ниже.
mid = left + (right - left) / 2
Вот математическое доказательство.
left + (right - left) / 2 = left / 1 + (right - left) / 2 // Making the denominators the same = (left * 2 + 1 * right - 1 * left) / (1 * 2) = (2left + right - left) / 2 = (left + right) / 2
Заворачивать
Итак, теперь вы знаете, как реализовать бинарный поиск и его различные варианты. Хотя временная сложность значительно выше, чем у линейного поиска, вы можете использовать хэш-таблицу, чтобы сделать его еще быстрее, что составляет O(1). Главный недостаток бинарного поиска заключается в том, что нам нужен отсортированный массив. С другой стороны, линейный поиск не требует отсортированного массива. Удачного кодирования!
Похожие сообщения.
