مثال على جافا باستخدام الانقسام للبحث والفرز

تنفيذ البحث ثنائي التفرع
تتطلب طريقة البحث الثنائي تسلسلًا مرتبة في الصفيف. البحث الثنائي هو أكثر من البحث الخطي: كلما زادت العناصر التي تكون فيها الصفيف ، كلما زادت الكفاءة. يتم التعبير عن كفاءة البحث الثنائي: O (log2n) n في نطاق الطاقة M من 2 ، وبالتالي فإن الحد الأقصى لعدد عمليات البحث هو M. log2n يعني أن قوة m 2 تساوي n ، حذف الثابت ، والاختصار كـ O (logn)
إذا كان هناك صفيف مطلوب من 200 عنصر ، فإن الحد الأقصى لعدد عمليات البحث الثنائية:
2^7 = 128 ، 2^8 = 256 ، يمكن ملاحظة أن قوة 7 لا يمكن أن تصل إلى 200 ، وتشمل قوة 8 ، وبالتالي فإن الحد الأقصى لعدد عمليات البحث يساوي 8

 // Loop ، Search Binary Static Int BinarySearch (int [] Array ، int data) {int start = 0 ؛ int end = array.length - 1 ؛ int mid = -1 ؛ بينما (ابدأ <= end) {system.out.println ("عدد عمليات البحث") ؛ mid = (start + end) >>> 1 ؛ if (Array [mid] <data) {start = mid + 1 ؛ } آخر إذا (Array [mid]> data) {end = mid - 1 ؛ } آخر {return mid ؛ } system.out.println ("start ="+start+"، end ="+end+"، mid ="+mid) ؛ } العودة -1 ؛ }

 // البحث الثنائي المتكرر البدء الأولي = 0 ، end = array.length - 1 static int binarySearch4Recursion (int [] artray ، int data ، 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) ؛ } آخر إذا (Array [mid]> data) {return BinarySearch4Recursion (Array ، Data ، Start ، Mid - 1) ؛ } آخر {return mid ؛ }}

نوع الإدراج ثنائي التفرع

هناك تسلسل A [0] ، a [1] ... a [n] ؛ حيث يتم طلب [I-1] بالفعل قبل ذلك. عند إدخال [i] ، استخدم الانقسام للبحث عن موضع كفاءة الإدراج [i]: o (n^2). بالنسبة للتسلسلات الأولية المطلوبة بشكل أساسي ، فإن الكفاءة ليست جيدة مثل فرز الإدراج المباشر ؛ للتسلسلات العشوائية والاضطراب ، تكون الكفاءة أعلى من فرز الإدراج المباشر.

 /** pipartite (مطوية ونصف) نوع الإدراج* تسلسل A [0] ، A [1] ... a [n] ؛ حيث يتم طلب [I-1] بالفعل قبل ذلك. عند إدخال [i] ، استخدم الانقسام للبحث عن موضع [i] insertion*/ public class binaryinsertsort {public static void main (string [] args) {int len ​​= 10 ؛ int [] ary = new int [len] ؛ عشوائي عشوائي = جديد عشوائي () ؛ لـ (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 ++) {// complexity n // حفظ القيمة الحالية int = ary [j] ؛ . 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 ++ ؛ } آري [الفهرس] = المفتاح ؛ setValueCount ++ ؛ } system.out.println ("/n عدد القيم (setValUeCount) =====>" + setValUeCount) ؛ } / *** البحث الثنائي عودة تصاعدي** param a ary* بالنظر إلى الصفيف المرتبة المراد البحث عنها* @param الهدف* ابحث عن الهدف* param من* نقطة انطلاق نطاق البحث الحالي* param إلى* نقطة العودة إلى المرجع للبحث الحالي عن الهدف* {int المدى = إلى - من ؛ // إذا كان النطاق أكبر من 0 ، أي أن هناك أكثر من عنصرين ، تابع الانقسام إذا (المدى> 0) {// حدد البت المتوسط ​​int mid = (to + from) / 2 ؛ // إذا لم يكن البتات الحاسمة غير راضية ، فاستمر في البحث عن ثنائي إذا كان (ARY [MID]> Target) {/ * * mid> الهدف ، القاعدة الصعودية ، الهدف أصغر ، ويجب تبديل الموضع ، أي ، يتم وضع الهدف في الوضع المتوسط ​​، * وفقًا لفكرة البحث ، من منتصف 1 ، يُعتبر أمرًا ، حتى = mid-1 */ return Bubinary Babyearchasc (Ary ، Target ، من Mid-1) ؛ } آخر { / * * mid <الهدف ، القاعدة الصعودية ، الهدف كبير ، ولا يتم تبادل أي مواضع. يجب أن يكون موضع البداية للبحث عن المقارنة منتصف + 1 */ return BinarySearchasc (ary ، الهدف ، منتصف + 1 ، إلى) ؛ }} آخر {if (ary [from]> target) {// على سبيل المثال ، 5،4 ، واحد لإدراج هو 4 عودة من ؛ } آخر {return from + 1 ؛ }}} / *** ترتيب تنازلي للبحث الثنائي ، متكرر* / ثابت int binarysearchdesc (int [] ary ، int ، int ، 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) ؛ } آخر {return BinarySearchDesc (ary ، target ، from ، mid - 1) ؛ }} else {if (ary [from]> target) {// على سبيل المثال ، 5،4 ، ما يجب إدراجه هو 4 عودة من + 1 ؛ } آخر {return from ؛ }}} / *** ترتيب تنازلي للبحث الثنائي ، غير متكرر* / static int binarysearchdesc2 (int [] ary ، int ، int from ، int to) {// بينما (من <إلى) {for ؛ from <to ؛) {int mid = (from +) >>> 1 ؛ if (ary [mid]> target) {from = mid + 1 ؛ } آخر {to = mid -1 ؛ }} // من <==> إلى ؛ if (ary [from]> target) {// if 5،4 ، واحد للإدراج هو 4 عودة من + 1 ؛ } آخر {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 موضع إدخال العنصر في الفهرس الأول هو: 1 918 562 442 531 210 216 931 706 333 إدراج العنصر في الفهرس الثالث هو: 2 918 562 531 442 210 216 931 706 333 132 موقف إدراج العنصر في الفهرس الرابع هو: 4 918 562 531 442 210 216 931 706 333 931 706 333 132 موضع إدخال العنصر في الفهرس السادس هو: 0 931 918 562 531 442 216 210 706 333 132 موضع إدراج العنصر في الفهرس السابع هو: 2 931 918 706 531 442 216 210 931 918 706 562 531 442 333 216 210 132 الموقع الذي سيتم فيه إدراج العنصر في الفهرس التاسع هو: 9

setValUeCount =====> 24

 931 918 706 562 531 442 333 216 210 132