| Главная » Статьи » Java » Java Ranger Basic |
День 11/21
| Binary Search Theory of Algorithms Теория алгоритмов – раздел информатики, изучающий общие свойства и закономерности алгоритмов и разнообразные формальные модели их представления. К задачам теории алгоритмов относятся формальное доказательство алгоритмической неразрешимости задач, асимптотический анализ сложности алгоритмов, классификация алгоритмов в соответствии с классами сложности, разработка критериев сравнительной оценки качества алгоритмов и т.п. Вместе с математической логикой теория алгоритмов образует теоретическую основу вычислительных наук. Binary Search Бинарный поиск – классический алгоритм поиска элемента в отсортированном массиве, использующий дробление массива на половины. Здесь реализован поиск элемента не полным перебором. Так, поделив изначальный массив 10 раз пополам (210 = 1024), мы уменьшаем искомую область в 1024 раз. А если к этому куску мы применим 10 делений, то финальный кусок будет в миллион раз меньше начального. Итого 30 делений приводят к уменьшению массива примерно в миллиард раз! В классе java.util.Arrays есть метод binarySearch(). Мы даем ему массив и элемент, позицию которого, нужно найти. Есть несколько переопределенных методов binarySearch – можно также указать с какого по какой индексы нужно проводить поиск. public static void main(String args) { int arr = {10, 20, 30, 40}; int pos1 = Arrays.binarySearch(arr, 20); int pos2 = Arrays.binarySearch(arr, 25); System.out.println(pos1); System.out.println(pos2); } >> 1 >> -3 Метод binarySearch должен работать с отсортированным массивом. Согласно документации, если оригинальный массив будет не отсортирован, то авторы ничего не гарантируют. Если binarySearch вернул отрицательное число, значит он не нашел то, что мы ищем. Причем само число будет указывать на индекс, где бы это число могло стоять. При этом индексы начинаются не с 0, а с -1 (это сделано для того, чтобы не было путаницы при результате 0, так как 0 = -0). То есть, если наше число не будет найдено, но оно могло бы быть в нулевой позиции, то нам вернут -1. Вот исходный код метода binarySearch: private static int binarySearch0(int a, int fromIndex, int toIndex, int key) { int low = fromIndex; int high = toIndex - 1; while (low <= high) { int mid = (low + high) >>> 1; int midVal = a[mid]; if (midVal < key) low = mid + 1; else if (midVal > key) high = mid - 1; else return mid; // key found } return -(low + 1); // key not found. } Также интересный пост от создателя JDK Джошуа Блоха Источник: http://becomejavasenior.com/courses/?utm_source=Java+Email+Courses&utm_campaign=aa710df388-JavaRangerBasicIntro&utm_medi | |
| Просмотров: 347 | | |
| Всего комментариев: 0 | |