Menerapkan pencarian dikotomis
Metode pencarian biner membutuhkan urutan yang dipesan dalam array. Pencarian biner lebih dari pencarian linier: semakin banyak elemen array, semakin jelas efisiensinya. Efisiensi pencarian biner diekspresikan: o (log2n) n berada dalam kisaran daya M 2, sehingga jumlah maksimum pencarian adalah M. log2n berarti bahwa kekuatan M 2 sama dengan n, hilangkan konstanta, dan disingkat o (logn)
Jika ada array yang dipesan dari 200 elemen, maka jumlah maksimum pencarian biner:
2^7 = 128, 2^8 = 256, dapat dilihat bahwa kekuatan 7 tidak dapat mencapai 200, dan kekuatan 8 termasuk, sehingga jumlah pencarian maksimum sama dengan 8
// loop, pencarian biner statis int binersearch (int [] array, int data) {int start = 0; int end = array.length - 1; int mid = -1; while (start <= end) {System.out.println ("Jumlah pencarian"); mid = (mulai + end) >>> 1; if (array [mid] <data) {start = mid + 1; } lain jika (array [mid]> data) {end = mid - 1; } else {return mid; } System.out.println ("start ="+start+", end ="+end+", mid ="+mid); } return -1; } // pencarian biner rekursif awal = 0, end = array.length - 1 static int binyersearch4recursion (int [] array, int data, int start, int end) {int mid = -1; System.out.println ("Jumlah Pencarian"); if (start> end) {return mid; } mid = (mulai + end) >>> 1; if (array [mid] <data) {return BinarySearch4Recursion (array, data, mid + 1, end); } lain jika (array [mid]> data) {return BinarySearch4Recursion (array, data, mulai, mid - 1); } else {return mid; }}Sortir penyisipan dikotomis
Ada urutan A [0], A [1] ... a [n]; di mana [I-1] sudah dipesan sebelumnya. Saat memasukkan [i], gunakan dikotomi untuk mencari posisi efisiensi penyisipan [i]: o (n^2). Untuk urutan awal yang dipesan, efisiensi tidak sebagus penyortiran penyisipan langsung; Untuk urutan acak dan tidak teratur, efisiensinya lebih tinggi dari penyortiran penyisipan langsung.
/** Bipartit (dilipat dan setengah) Penyisipan Sort* urutan a [0], a [1] ... a [n]; di mana [I-1] sudah dipesan sebelumnya. Ketika [i] dimasukkan, gunakan dikotomi untuk mencari posisi penyisipan [i]*/ kelas publik BinaryInsertSort {public static void main (string [] args) {int len = 10; int [] ary = int [len] baru; Acak acak = acak baru (); untuk (int j = 0; j <len; j ++) {ary [j] = random.nextInt (1000); } BinaryInsert (ARY); / * * Analisis Kompleksitas: Dalam kasus terbaik, yaitu, semua telah diurutkan, tidak perlu bergerak dengan benar. Pada saat ini, kompleksitas waktu adalah: o (n lg n) kasus terburuk adalah, semua urutan terbalik, dan pada saat ini kompleksitasnya adalah O (n^2) * Kompleksitas kasus terburuk tidak dapat ditingkatkan menjadi O (n | logn). */ // cetak printarray array (ary); } / *** Masukkan sortir* @param ary* / private static void binaryinsert (int [] ary) {int setValueCount = 0; // Sortir dari elemen kedua array, karena elemen pertama itu sendiri harus diurutkan untuk (int j = 1; j <ary.length; j ++) {// kompleksitas n // simpan nilai int int saat ini = ary [j]; // ∆ Gunakan pencarian biner untuk menemukan posisi penyisipan // int index = BinarySearchasc (ary, ary [j], 0, j - 1); // kompleksitas: o (logn) // index = BinarySearchDesc (ary, ary [j], 0, j - 1); // kompleksitas: o (logn) inter index = biner = biner = biner2, j - j - 1); // kompleksitas: o (logn) inter index = biner = Biner = Bineres (j - j - 1); // kompleksitas: O (LOGN) INT INDEX = BINARING = BINARY = BINARING = BINARING = BINARING2, J - 1);/ 1); // kompleksitas: o (logn) printarray (ary); System.out.println ("" +j +"indeks yang akan dimasukkan pada posisi:" +indeks); // Masukkan target ke posisi, dan geser elemen ke kanan posisi target kanan pada saat yang sama untuk (int i = j; i> index; i--) {// kompleksitas, kasus terburuk: (n-1)+(n-2)+...+n/2 = o (n^2) ary [i] = ary [i-1]; // I-1 <==> indeks setValuecount ++; } ary [index] = key; setValuecount ++; } System.out.println ("/n Jumlah nilai (setValuecount) ======>" + setValuecount); } /** * Binary search ascending recursion* * @param a ary * Given the sorted array to be looked up* @param target * Find the target* @param from * The starting point of the range of the current search* @param to * The return end point of the current search* @return Return the target in the array, where it should be in order*/ private static int binarySearchAsc(int[] ary, int target, int from, int to) {int range = to - from; // Jika kisarannya lebih besar dari 0, yaitu, ada lebih dari dua elemen, lanjutkan untuk membagi IF (rentang> 0) {// Pilih bit intermediate int mid = (ke + dari) / 2; // If the critical bit is not satisfied, continue to search binary if (ary[mid] > target) { /* * mid > target, ascending rule, target is smaller, and the position should be swapped, that is, target is positioned at the mid position, * According to the search idea, from from to mid-1, it is considered orderly, so to=mid-1 */ return binarySearchAsc(ary, target, from, mid - 1); } else { / * * mid <target, aturan naik, target besar, dan tidak ada posisi yang dipertukarkan. Posisi awal untuk mencari perbandingan harus mid + 1 */ return BinarySearchasc (ary, target, mid + 1, to); }} else {if (ary [from]> target) {// misalnya, 5,4, yang dimasukkan adalah 4 kembali dari; } else {kembali dari + 1; }}} / *** Pencarian Biner Pencarian Descending Order, Recursive* / Private Static Int BinarySearchDesc (int [] ary, int target, int from, int to) {int range = to - from; if (range> 0) {int mid = (from + to) >>> 1; if (ary [mid]> target) {return BinarySearchDesc (ary, target, mid + 1, to); } else {return BinarySearchDesc (ary, target, dari, mid - 1); }} else {if (ary [from]> target) {// misalnya, 5,4, apa yang harus dimasukkan adalah 4 kembali dari + 1; } else {return from; }}} / *** Pencarian Biner Pencarian Descending Order, Non-Recursive* / Private Static Int BinarySearchDesc2 (int [] ary, int target, int from, int to) {// while (dari <to) {for (; from <to;) {int mid = (from + to) >>> 1; if (ary [mid]> target) {from = mid + 1; } else {to = mid -1; }} // dari <==> ke; if (ary [from]> target) {// jika 5,4, yang disisipkan adalah 4 kembali dari + 1; } else {return from; }} private static void printArray (int [] ary) {for (int i: ary) {System.out.print (i + ""); }}}Mencetak
918 562 442 531 210 216 931 706 333 132 Posisi penyisipan elemen pada indeks pertama adalah: 1 918 562 442 531 210 216 931 706 333 132 dari Posisi 210.220.220.220.220.220.22.3. Elemen pada indeks ketiga adalah: 2 918 562 531 442 210 216 931 706 333 132 Posisi penyisipan elemen pada indeks keempat adalah: 4 918 562 531 442 210 216 931 706 333 132.IM POSIS POSISI PENGGABUNGAN ON Fifth Index pada Indeks Kelima: 4 93. 4 96.4.4. 333 132 Posisi penyisipan elemen pada indeks keenam adalah: 0 931 918 562 531 442 216 210 706 333 132 Posisi penyisipan elemen pada indeks ketujuh adalah: 2 931 918 706 562 ENDIRAN 442 216 210 333 132 POSIS POSIS POSISI 562 531 442 216 210 333 132 POSIS POSISI 662 DARI 531. 562 531 442 333 216 210 132 Lokasi di mana elemen pada indeks ke -9 harus dimasukkan adalah: 9
SetValuecount =====> 24
931 918 706 562 531 442 333 216 210 132