لقد كان البحث الخطي في Java دائمًا هو الأسلوب الأمثل للعثور على عنصر في مصفوفة. فهو يبحث في كل عنصر من عناصر المصفوفة بالتسلسل وهو سهل التنفيذ للغاية. ومع ذلك، فإن عيوب البحث الخطي تكون واضحة عندما تحتوي المصفوفة المعنية على عشرات الآلاف من العناصر. في مثل هذه الحالات، تكون طريقة "فرق تسد" التي يطبقها البحث الثنائي أكثر كفاءة ومفضلة للمبرمجين مع مراعاة تعقيد الزمان والمكان.
بحث ثنائي
في البحث الثنائي، يتم تقسيم المصفوفة بشكل متكرر إلى نصفين حتى يتم العثور على المفتاح (العنصر الذي يتم البحث عنه). يكون التقسيم افتراضيًا، أي يتم الحفاظ على سلامة البيانات. مع كل تكرار، يتم التركيز على القيمة الوسطى للمصفوفة. إذا كانت القيمة مساوية للمفتاح الذي نبحث عنه، تنتهي الحلقة أو الدالة العودية. وإلا فإنه يستمر في التكرار. إذا كانت القيمة الوسطى أكبر من المفتاح، فستركز الدالة بعد ذلك على النصف الأول من المصفوفة والعكس صحيح. تتكرر هذه العملية حتى يتم العثور على المفتاح أو تكرار المصفوفة بأكملها.
الفرق بين البحث الخطي والثنائي
البحث الخطي |
بحث ثنائي |
يبحث بالتسلسل في المصفوفة |
يقسم المصفوفة إلى نصفين حتى يتم العثور على القيمة |
يعمل مع أي مجموعة |
يعمل فقط مع المصفوفات التي تم فرزها |
التعقيد هو O(N) |
التعقيد هو O(log2N) |
يمكن أن تعمل على المصفوفات المصنفة وغير المصنفة |
لا يمكن تنفيذها إلا على المصفوفات التي تم فرزها. |
أقل تعقيدًا في التنفيذ |
أكثر تعقيدا في التنفيذ |
خوارزمية البحث الثنائية
خوارزمية البحث الثنائي موضحة أدناه.
- تحديد النقطتين الأولى والأخيرة من المصفوفة. سيتم تعديل النقاط عند كل تكرار حسب المصفوفة والمفتاح الذي يتم البحث عنه.
- كرر خلال المصفوفة وقارن القيمة الوسطى بين النقطتين الأولى والأخيرة الحاليتين. في التكرار الأول، سيكون المتغير الأول والأخير هو نفس المتغير الفعلي في المصفوفة.
- إذا كان المفتاح أكبر من القيمة الوسطى، فسيتم تخزين فهرس تلك القيمة في المتغير "الأول" الجديد.
- إذا كان المفتاح أقل من القيمة الوسطى، فسيتم تخزين فهرس تلك القيمة في المتغير "الأخير".
- ويتكرر هذا الشرط حتى يتحقق أحد الشرطين:
- تم العثور على المفتاح.
- لقد تم تكرار المصفوفة بأكملها.
الكود لكل من البحث الثنائي التكراري والبحث الثنائي العودي موضح أدناه.
البحث الثنائي التكراري
رمز البحث الثنائي بطريقة تكرارية موضح أدناه.
import java.util.Scanner;
public class IterativeBinarySearch {
public static void main(String[] args) {
int arr[] = {1,3,6,8,10};
System.out.println("Enter Number to Search For: ");
Scanner input = new Scanner (System.in);
int num = input.nextInt();
int result = BinarySearchIterative(arr,num);
if(result!=-1)
System.out.println("Value Found at Index #" + result);
else
System.out.println("Value Not Found");
}
public static int BinarySearchIterative(int[] arr, int num){
int start = 0;
int end = arr.length;
for(int i = 0; iarr[n]){
start = n;
}
else{
end = n;
}
}
return -1;
}
}
البحث الثنائي العودي
ويرد أدناه رمز ثنائي باستخدام العودية.
import java.util.Scanner;
public class RecursiveBinarySearch {
public static void main(String[] args) {
int arr[] = {1,3,6,8,10};
System.out.println("Enter Number to Search For: ");
Scanner input = new Scanner (System.in);
int num = input.nextInt();
int result = BinarySearchRecursive(arr,0,arr.length-1,num);
if(result!=-1)
System.out.println("Value Found at Index #" + result);
else
System.out.println("Value Not Found");
}
public static int BinarySearchRecursive(int arr[], int a, int b, int num){
if (b < 1) {
return -1;
}
int n = a + (b=1)/2;
if(arr[n]==num)
return n;
else if(arr[n]>num)
return BinarySearchRecursive(arr,a,n-1,num);
else
return BinarySearchRecursive(arr,n+1,b,num);
}
}
تعقيد الوقت
مع كل تكرار، يتم تقسيم المصفوفة، أي مساحة البحث إلى النصف. بعد كل تكرار 'm'، ستتغير مساحة البحث إلى حجم N/2m. في أسوأ السيناريوهات، لن يتبقى لنا سوى عنصر واحد على جانب واحد بعيد من المصفوفة. في هذا الوقت، سيكون تعقيد البحث الثنائي هو k = log2N. التعقيد الزمني للبحث الخطي هو O(N) مما يؤدي إلى أن يكون البحث الثنائي أسرع بكثير مع التعقيد O(log2N). هذه هي الفائدة الأساسية لاستخدام البحث الثنائي بدلاً من البحث الخطي.
تعقيد الفضاء
يستخدم البحث الثنائي ثلاثة متغيرات مختلفة - البداية والنهاية والوسط. يتم إنشاء هذه المتغيرات الثلاثة كمؤشرات تشير إلى موقع الذاكرة الخاص بمؤشرات المصفوفة. ونتيجة لهذا، يعتبر البحث الثنائي فعالاً للغاية فيما يتعلق بالمساحة. التعقيد المكاني للبحث الثنائي التكراري هو O(1). بالنسبة للتنفيذ العودي، فهو O(log N).
GO TO FULL VERSION