Реализовать дихотомический поиск
Метод бинарного поиска требует упорядоченной последовательности в массиве. Бинарный поиск - это больше, чем линейный поиск: чем больше элементов массив, тем более очевидна эффективность. Эффективность бинарного поиска выражена: O (log2n) N находится в диапазоне M мощности 2, поэтому максимальное количество поисков составляет M. log2n, что мощность M 2 равен N, опускает константу и сокращена как O (logn)
Если есть упорядоченный массив из 200 элементов, то максимальное количество бинарных поисков:
2^7 = 128, 2^8 = 256, видно, что мощность 7 не может достичь 200, а мощность 8 включает в себя, поэтому максимальное количество поисков равна 8
// цикл, двоичный поиск static int binarysearch (int [] array, int data) {int start = 0; int end = array.length - 1; int mid = -1; while (start <= end) {System.out.println ("Количество поисков"); mid = (start + end) >>> 1; if (array [mid] <data) {start = mid + 1; } else if (array [mid]> data) {end = mid - 1; } else {return mid; } System.out.println ("start ="+start+", end ="+end+", mid ="+mid); } return -1; } // Рекурсивный бинарный поиск начальный старт = 0, end = array.length - 1 static int binarysearch4recursion (int [] массив, int data, int neth, int end) {int mid = -1; System.out.println ("количество поисков"); if (start> end) {return mid; } mid = (start + end) >>> 1; if (array [mid] <data) {return binarysearch4recursion (массив, данные, Mid + 1, End); } else if (array [mid]> data) {return binarysearch4recursion (массив, данные, начало, mid - 1); } else {return mid; }}Дихотомическая вставка
Существует последовательность A [0], a [1] ... a [n]; где [I-1] уже заказан перед ним. При вставке [i] используйте дихотомию для поиска позиции [I] эффективности вставки: O (n^2). Для первоначальных в основном упорядоченных последовательностей эффективность не так хороша, как прямая сортировка вставки; Для случайных и неупорядоченных последовательностей эффективность выше, чем прямая сортировка вставки.
/** Двухпартийное (сложенное и половина) вставка сортировки* последовательность a [0], a [1] ... a [n]; где [I-1] уже заказан перед ним. Когда вставлен [i], используйте дихотомию для поиска позиции [i] вставки*/ public class binaryinsertsort {public static void main (string [] args) {int len = 10; int [] ary = new int [len]; Случайный случайный = new Random (); for (int j = 0; j <len; j ++) {ary [j] = random.nextint (1000); } binaryinsert (ary); / * * Анализ сложности: в лучшем случае, то есть все было отсортировано, нет необходимости двигаться правильно. В настоящее время сложность времени: O (n lg n) худший случай, все обратное порядка, и в настоящее время сложность o (n^2) * Сложность наихудшего случая не может быть улучшена до O (n | logn). */ // Распечатать массив Printarray (ary); } / *** Вставьте сортировку* @param ary* / private static void binaryinsert (int [] ary) {int setValueCount = 0; // Сортировка со второго элемента массива, потому что сам первый элемент должен быть сортирован для (int j = 1; j <ary.length; j ++) {// Сложность n // Сохранить текущее значение int key = ary [j]; // ∆ Используйте двоичный поиск, чтобы найти позицию вставки // int index = binarysearchasc (ary, ary [j], 0, j - 1); // Сложность: o (logn) // int index = binarysearchdesc (ary, ary [j], 0, j - 1); // сложно: o (logn) index = binarysearcDes 1); // Сложность: o (logn) printarray (ary); System.out.println ("" +j +"Индексы для вставки в позицию:" +index); // вставить цель в положение и сдвинуть элемент справа от целевой позиции в то же время для (int i = j; i> index; i--) {// Сложность, худший случай: (n-1)+(n-2)+...+n/2 = O (n^2) ary [i] = ary [i-1]; // i-1 <==> index setValueCount ++; } ary [index] = key; setValueCount ++; } System.out.println ("/n Количество значений (setValueCount) ====>" + setValueCount); } / *** двоичный поиск по восхождению рекурсии** @param a ary*, учитывая отсортированный массив, который будет рассмотрен, чтобы найти* @param target* Найдите цель* @param из* отправной точки диапазона текущего поиска* @param to* return end neccrent search* @return Вернуть цель в целевом, где он должен быть в порядке* / private static int byrarysearch (int, int, int, int, int, int, int, int, int, int, int, int, int, int, int, int, int, int, in int, in in in in in int intearyseary. {int range = to - from; // Если диапазон больше 0, то есть существует более двух элементов, продолжайте разделить, если (диапазон> 0) {// выберите промежуточный бит int mid = (до + из) / 2; // Если критический бит не удовлетворен, продолжайте искать бинарный, if (ary [mid]> target) {/ * * mid> target, восходящее правило, цель меньше, а позиция должна быть заменена, то есть цель позиционируется в средней позиции, * в соответствии с идеей поиска, от Mid-1, считается порядок, так что для = Mid-1/ return BiardiSearchAss (ARY, Target, от Mid, 1); } else { / * * mid <цель, правило восходящего, цель большая, и никакие позиции не обмениваются. Начальная позиция для поиска сравнения должна быть MID + 1 */ return BinarySearchasc (Ary, Target, Mid + 1, To); }} else {if (ary [from]> target) {// Например, 5,4, один для вставки - 4 возврата из; } else {return from + 1; }}} / *** двоичный поиск по порядку убывания, рекурсивный* / private static int binarysearchdesc (int [] ary, int target, int of, int to) {int range = to - from; if (диапазон> 0) {int mid = (от + до) >>> 1; if (ary [mid]> target) {return binarysearchdesc (ary, target, mid + 1, to); } else {return binarysearchdesc (ary, target, from, mid - 1); }} else {if (ary [from]> target) {// Например, 5,4, то, что должно быть вставлено, - это 4 возврата из + 1; } else {return from; }}} / *** двоичный поиск по порядку убывания, нерекурсирующий* / private static int binarysearchdesc2 (int [] ary, int target, int от, int to) {// while (from) {for (f от <to;) {int mid = (от + до) >>> 1; if (ary [mid]> target) {from = mid + 1; } else {to = mid -1; }} // от <==> to; if (ary [from]> target) {// Если 5,4, то, что для вставки, 4 возврата из + 1; } else {return from; }} private static void printarray (int [] ary) {for (int i: ary) {System.out.print (i + ""); }}}Печать
918 562 442 531 210 216 931 706 333 132 The position of insertion of the element on the first index is: 1 918 562 442 531 210 216 931 706 333 132 The position of insertion of the element on the second index is: 2 918 562 442 531 210 216 931 706 333 132 The position of Вставка элемента по третьему индексу: 2 918 562 531 442 210 216 931 706 333 132 210 931 706 333 132. Положение вставки элемента в шестом индексе: 0 931 918 562 531 442 216 210 706 333 132 Положение элемента на седьмом индексе: 2 931 918 706 562 531 442 216 210 3333331. Индекс: 6 931 918 706 562 531 442 333 216 210 132 Место, где должен быть вставлен элемент на 9 -м индексе: 9
SetValueCount =====> 24
931 918 706 562 531 442 333 216 210 132