ใช้การค้นหาแบบแบ่งขั้ว
วิธีการค้นหาแบบไบนารีต้องมีลำดับที่สั่งซื้อในอาร์เรย์ การค้นหาแบบไบนารีเป็นมากกว่าการค้นหาเชิงเส้น: ยิ่งองค์ประกอบของอาร์เรย์มากเท่าไหร่ก็ยิ่งมีประสิทธิภาพมากขึ้นเท่านั้น ประสิทธิภาพของการค้นหาแบบไบนารีแสดง: O (log2n) n อยู่ในช่วงพลังงาน M ของ 2 ดังนั้นจำนวนสูงสุดของการค้นหาคือ M. log2n หมายความว่าพลังงาน M ของ 2 เท่ากับ n, ละเว้นค่าคงที่และตัวย่อเป็น O (LOGN)
หากมีอาร์เรย์ที่สั่งซื้อ 200 องค์ประกอบดังนั้นจำนวนสูงสุดของการค้นหาไบนารี:
2^7 = 128, 2^8 = 256 จะเห็นได้ว่าพลังของ 7 ไม่สามารถเข้าถึงได้ 200 และพลังของ 8 รวมอยู่ด้วยดังนั้นจำนวนการค้นหาสูงสุดเท่ากับ 8
// loop, การค้นหาแบบไบนารี int binarySearch (int [] อาร์เรย์, ข้อมูล int) {int start = 0; int end = array.length - 1; int mid = -1; ในขณะที่ (start <= end) {system.out.println ("จำนวนการค้นหา"); mid = (start + end) >>> 1; if (array [mid] <data) {start = mid + 1; } อื่นถ้า (อาร์เรย์ [mid]> data) {end = mid - 1; } else {return mid; } system.out.println ("start ="+start+", end ="+end+", mid ="+mid); } return -1; - // การค้นหาแบบไบนารีแบบเรียกซ้ำเริ่มต้น = 0, end = array.length - 1 int int binarySearch4Recursion (int [] อาร์เรย์, ข้อมูล int, int start, int end) {int mid = -1; System.out.println ("จำนวนการค้นหา"); if (start> end) {return mid; } mid = (start + end) >>> 1; if (array [mid] <data) {return binarySearch4Recursion (array, data, mid + 1, end); } อื่นถ้า (อาร์เรย์ [mid]> data) {return binarySearch4Recursion (อาร์เรย์, ข้อมูล, เริ่มต้น, กลาง - 1); } else {return mid; -เรียงลำดับการแทรกแบบคู่
มีลำดับ A [0], A [1] ... A [n]; โดยที่ [I-1] ได้รับคำสั่งก่อนหน้านี้ เมื่อแทรก [i] ให้ใช้การแบ่งขั้วเพื่อค้นหาตำแหน่งของ [i] ประสิทธิภาพการแทรก: o (n^2) สำหรับลำดับแรกที่สั่งซื้อโดยทั่วไปประสิทธิภาพไม่ดีเท่ากับการเรียงลำดับการแทรกโดยตรง สำหรับลำดับแบบสุ่มและไม่เป็นระเบียบประสิทธิภาพจะสูงกว่าการเรียงลำดับการแทรกโดยตรง
/** bipartite (พับและครึ่ง) เรียงลำดับการเรียง* ลำดับ a [0], a [1] ... a [n]; โดยที่ [I-1] ได้รับคำสั่งก่อนหน้านี้ เมื่อใส่ [i] ให้ใช้การแบ่งขั้วเพื่อค้นหาตำแหน่งของการแทรก [i]*/ คลาสสาธารณะ binaryinsertsort {โมฆะคงที่สาธารณะหลัก (สตริง [] args) {int len = 10; int [] ary = new int [len]; สุ่มสุ่ม = ใหม่สุ่ม (); สำหรับ (int j = 0; j <len; j ++) {ary [j] = random.nextint (1,000); } BinaryInsert (ARY); / * * การวิเคราะห์ความซับซ้อน: ในกรณีที่ดีที่สุดนั่นคือทั้งหมดได้รับการจัดเรียงไม่จำเป็นต้องย้ายถูกต้อง ในเวลานี้ความซับซ้อนของเวลาคือ: o (n lg n) กรณีที่เลวร้ายที่สุดคือลำดับย้อนกลับทั้งหมดและในเวลานี้ความซับซ้อนคือ o (n^2) * ความซับซ้อนของกรณีที่เลวร้ายที่สุดไม่สามารถปรับปรุงเป็น o (n | logn) */ // พิมพ์อาร์เรย์ printarray (ary); } / *** แทรกการเรียงลำดับ* @param ary* / โมฆะคงที่ส่วนตัว 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); 1); // ความซับซ้อน: o (logn) printarray (ary); System.out.println ("" +j +"ดัชนีที่จะแทรกที่ตำแหน่ง:" +ดัชนี); // แทรกเป้าหมายลงในตำแหน่งและเลื่อนองค์ประกอบไปทางขวาของตำแหน่งเป้าหมายในเวลาเดียวกันสำหรับ (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 [ดัชนี] = คีย์; SetValUecount ++; } system.out.println ("/n จำนวนของค่า (setValUecount) =====>" + setValUecount); } / *** การค้นหาแบบไบนารีจากน้อยไปมาก** @param a ary* ได้รับอาเรย์ที่เรียงลำดับเพื่อค้นหา* @param เป้าหมาย* ค้นหาเป้าหมาย* @param จาก* จุดเริ่มต้นของช่วงของการค้นหาปัจจุบัน* @param ถึง* จุดสิ้นสุดการค้นหาในปัจจุบัน {int range = to - จาก; // ถ้าช่วงมากกว่า 0 นั่นคือมีมากกว่าสององค์ประกอบให้แยกต่อไปหาก (ช่วง> 0) {// เลือกบิตกลาง int กลาง = (ถึง + จาก) / 2; // หากบิตวิกฤตไม่พอใจให้ค้นหาไบนารีไบนารีต่อไปหาก (ARY [กลาง]> เป้าหมาย) {/ * * กลาง> เป้าหมายขึ้นไปเป้าหมายนั้นมีขนาดเล็กลงและตำแหน่งควรเปลี่ยนนั่นคือเป้าหมายอยู่ที่ตำแหน่งกลาง } else { / * * mid <เป้าหมาย, กฎน้อยไปมาก, เป้าหมายมีขนาดใหญ่และไม่มีการแลกเปลี่ยนตำแหน่ง ตำแหน่งเริ่มต้นสำหรับการค้นหาการเปรียบเทียบควรเป็น mid + 1 */ return binarysearchasc (ary, target, mid + 1, ถึง); }} else {if (ary [จาก]> target) {// ตัวอย่างเช่น 5,4, หนึ่งที่จะแทรกคือ 4 return จาก; } else {กลับจาก + 1; }}} / *** ลำดับการค้นหาไบนารีลง, เรียกซ้ำ* / ส่วนตัวคงที่ int binarySearchDesc (int [] ary, int เป้าหมาย, int จาก, int ถึง) {int range = to - จาก; ถ้า (ช่วง> 0) {int mid = (จาก + ถึง) >>> 1; if (ary [mid]> target) {return binarySearchDesc (ary, target, mid + 1, ถึง); } else {return BinarySearchDesc (ary, target, จาก, mid - 1); }} else {if (ary [จาก]> เป้าหมาย) {// ตัวอย่างเช่น 5,4 สิ่งที่ต้องแทรกคือ 4 คืนจาก + 1; } else {return จาก; }}} / *** ลำดับการค้นหาไบนารีลง, ไม่ได้รับการตอบโต้* / ส่วนตัว int binarySearchDesc2 (int [] ary, int เป้าหมาย, int จาก, int ถึง) {// ในขณะที่ (จาก <ถึง) {สำหรับ (; จาก <to;) {int mid = (จาก + ถึง) >>>> if (ary [mid]> เป้าหมาย) {จาก = mid + 1; } else {to = mid -1; }} // จาก <==> ถึง; if (ary [จาก]> target) {// ถ้า 5,4 หนึ่งที่จะแทรกคือ 4 return จาก + 1; } else {return จาก; }} printArray แบบคงที่ส่วนตัว (int [] ary) {สำหรับ (int i: ary) {system.out.print (i + ""); -พิมพ์
918 562 442 531 210 216 931 706 333 132 ตำแหน่งของการแทรกขององค์ประกอบในดัชนีแรกคือ: 1 918 562 442 531 210 216 931 706 333 132 ตำแหน่งการแทรกขององค์ประกอบที่สองคือ: 2 918 562 562 การแทรกขององค์ประกอบในดัชนีที่สามคือ: 2 918 562 531 442 210 216 931 706 333 132 ตำแหน่งของการแทรกขององค์ประกอบในดัชนีที่สี่คือ: 4 918 562 531 442 210 216 931 706 333 132 931 706 333 132 ตำแหน่งของการแทรกขององค์ประกอบในดัชนีที่หกคือ: 0 931 918 562 531 442 216 210 706 333 132 ตำแหน่งของการแทรกขององค์ประกอบในดัชนีที่เจ็ด 132. 931 918 706 562 531 442 333 216 210 132 ตำแหน่งที่องค์ประกอบในดัชนี 9 จะต้องแทรกคือ: 9
SetValUecount =====> 24
931 918 706 562 531 442 333 216 210 132