كيفية تنفيذ خوارزمية بحث ثنائي في جافا دون تكرار

تطبيق تكراري لخوارزمية البحث الثنائي الشائعة للعثور على عنصر في مصفوفة مرتبة.

مرحبا جميعا! لقد قمت بنشر الكثير من الخوارزميات ومقالات بنية البيانات على مدونتي ، ولكن هذه المقالة هي الأولى هنا. في هذه المقالة ، سنفحص الخوارزميات الأساسية الشائعة لإجراء المقابلات.

نعم ، لقد خمنت الأمر بشكل صحيح: تحتاج إلى تنفيذ بحث ثنائي في Java ، وتحتاج إلى كتابة خوارزميات بحث ثنائية تكرارية ومتكررة.

في علوم الكمبيوتر ، يعد البحث الثنائي ، أو البحث نصف الفاصل ، خوارزمية فرق تسد التي تحدد موضع عنصر في مصفوفة مرتبة. يعمل البحث الثنائي من خلال مقارنة قيمة الإدخال بالعنصر الأوسط في المصفوفة.

تحدد المقارنة ما إذا كان العنصر يساوي الإدخال ، أو أقل من الإدخال ، أو أكبر من المدخل.

عندما يساوي العنصر الذي تتم مقارنته الإدخال ، يتوقف البحث ويعيد عادةً موضع العنصر.

إذا كان العنصر لا يساوي المدخلات ، فعندئذٍ يتم إجراء مقارنة لتحديد ما إذا كان الإدخال أقل من العنصر أو أكبر منه.

اعتمادًا على النتيجة ، تبدأ الخوارزمية من جديد ، ولكن تبحث فقط في الجزء العلوي أو السفلي من مجموعة عناصر المصفوفة.

إذا لم يكن الإدخال موجودًا داخل المصفوفة ، فستخرج الخوارزمية عادةً قيمة فريدة تشير إلى ذلك مثل -1 أو مجرد طرح RuntimeException في Java مثل NoValueFoundException.

عادةً ما تخفض خوارزميات البحث الثنائي عدد العناصر التي يجب التحقق منها مع كل تكرار متتالي إلى النصف ، وبالتالي تحديد موقع العنصر المحدد (أو تحديد غيابه) في الوقت اللوغاريتمي.

راجع للشغل ، إذا لم تكن معتادًا على خوارزميات البحث والفرز الأساسية ، فيمكنك أيضًا الانضمام إلى دورة مثل هياكل البيانات والخوارزميات: الغوص العميق باستخدام Java لتعلم الخوارزميات الأساسية.

إذا لم تكن Java هي اختيارك للغة ، يمكنك العثور على مزيد من التوصيات لجافا سكريبت وبايثون في قائمة دورات الخوارزميات هذه.

بالمناسبة ، إذا كنت تفضل الكتب ، أقترح عليك قراءة كتاب خوارزمية شامل مثل مقدمة إلى الخوارزميات من تأليف توماس إتش كورمين.

فيما يلي بعض نماذج التعليمات البرمجية التي تُظهر منطق البحث الثنائي التكراري في Java :

تنفيذ البحث الثنائي في جافا

فيما يلي نموذج لبرنامج لتنفيذ البحث الثنائي في Java. يتم تنفيذ الخوارزمية بشكل متكرر. أيضًا ، هناك حقيقة مثيرة للاهتمام يجب معرفتها حول تنفيذ البحث الثنائي في Java وهي أن Joshua Bloch ، مؤلف كتاب Java الفعال الشهير ، كتب البحث الثنائي في "java.util.Arrays".

import java.util.Arrays;import java.util.Scanner;
/** * Java program to implement Binary Search. We have implemented Iterative* version of Binary Search Algorithm in Java** @author Javin Paul*/
public class IterativeBinarySearch {
 public static void main(String args[]) { int[] list = new int[]{23, 43, 31, 12}; int number = 12; Arrays.sort(list); System.out.printf("Binary Search %d in integer array %s %n", number, Arrays.toString(list));
 binarySearch(list, 12); System.out.printf("Binary Search %d in integer array %s %n", 43, Arrays.toString(list));
 binarySearch(list, 43); list = new int[]{123, 243, 331, 1298}; number = 331; Arrays.sort(list); System.out.printf("Binary Search %d in integer array %s %n", number, Arrays.toString(list));
 binarySearch(list, 331); System.out.printf("Binary Search %d in integer array %s %n", 331, Arrays.toString(list)); binarySearch(list, 1333);
 // Using Core Java API and Collection framework // Precondition to the Arrays.binarySearch Arrays.sort(list);
 // Search an element int index = Arrays.binarySearch(list, 3);
}
/** * Perform a binary Search in Sorted Array in Java * @param input * @param number * @return location of element in array */
public static void binarySearch(int[] input, int number) {int first = 0;int last = input.length - 1;int middle = (first + last) / 2;
while (first <= last) { if (input[middle] < number) { first = middle + 1;} else if (input[middle] == number) {
System.out.printf(number + " found at location %d %n", middle);break;} else { last = middle - 1;}
middle = (first + last) / 2;
}
if (first > last) { System.out.println(number + " is not present in the list.\n");}
}
}
OutputBinary Search 12 in integer array [12, 23, 31, 43]12 found at location 0Binary Search 43 in integer array [12, 23, 31, 43]43 found at location 3Binary Search 331 in integer array [123, 243, 331, 1298]331 found at location 2Binary Search 331 in integer array [123, 243, 331, 1298]1333 is not present in the list.

هذا كل شيء عن كيفية تنفيذ البحث الثنائي باستخدام العودية في Java . إلى جانب البحث الخطي ، هذان هما من خوارزميات البحث الأساسية التي تتعلمها في فصل علوم الكمبيوتر.

تستفيد بنية بيانات شجرة البحث الثنائية من هذه الخوارزمية وترتب البيانات في بنية هرمية بحيث يمكنك البحث في أي عقدة في وقت O (logN).

على الرغم من ذلك ، يجب أن تتذكر أنه من أجل استخدام البحث الثنائي ، فأنت بحاجة إلى قائمة أو مصفوفة مرتبة ، لذلك تحتاج أيضًا إلى التفكير في تكلفة الفرز عندما تفكر في استخدام خوارزمية البحث الثنائي في العالم الحقيقي.

مزيد من التعلم

هياكل البيانات والخوارزميات: الغوص العميق باستخدام Java

الخوارزميات وهياكل البيانات - الجزء 1 و 2

هياكل البيانات في Java 9 بواسطة Heinz Kabutz

10 كتب خوارزميات للمقابلات

10 دورات في هيكل البيانات والخوارزمية للمقابلات

5 دورات مجانية لتعلم هياكل البيانات والخوارزميات

برامج تعليمية أخرى حول بنية البيانات والخوارزميات قد تعجبك

  • كيف يتم تطبيق خوارزمية Quicksort في جافا؟ (الدورة التعليمية)
  • كيفية تنفيذ شجرة البحث الثنائية في جافا؟ (المحلول)
  • كيفية تنفيذ خوارزمية Quicksort دون العودية؟ (الدورة التعليمية)
  • كيفية تنفيذ خوارزمية فرز الإدراج في جافا؟ (الدورة التعليمية)
  • كيفية تنفيذ خوارزمية الفرز الفقاعي في جافا؟ (الدورة التعليمية)
  • ما هو الفرق بين خوارزمية الفرز القائمة على المقارنة وغير المقارنة؟ (إجابة)
  • كيف يتم تنفيذ Bucket Sort في Java؟ (الدورة التعليمية)
  • كيفية تنفيذ خوارزمية بحث ثنائي بدون تكرار في جافا؟ (الدورة التعليمية)
  • أكثر من 50 دورة في بنية البيانات والخوارزميات للمبرمجين (أسئلة)

شكرا لقراءة هذا المقال. إذا أعجبك هذا المقال ، فيرجى مشاركته مع أصدقائك وزملائك. إذا كان لديك أي اقتراح أو ملاحظات ، فيرجى ترك تعليق.

ملاحظة - إذا كنت جادًا في تحسين مهاراتك في الخوارزميات ، فأعتقد أن هياكل وخوارزميات البيانات: الغوص العميق باستخدام Java هو أفضل ما تبدأ به.