البحث: الخطي والثنائي
تحتاج هذه الصفحة إلى متصفح حديث (يدعم SharedArrayBuffer). يرجى تحديث Chrome أو Edge أو Firefox أو Safari إلى أحدث إصدار.
إيجاد قيمة
- مهمة شائعة هي البحث: هل توجد قيمة في مصفوفة، وأين؟
- الإجابة المعتادة هي الفهرس الذي وجدنا فيه القيمة، أو
-1إذا لم تكن موجودة. - نتعلم طريقتين: البحث الخطي (يعمل على أي مصفوفة) والبحث الثنائي (يتطلب مصفوفة مرتبة، ولكنه أسرع بكثير).
البحث الخطي
- انظر إلى كل عنصر من الفهرس
0حتى النهاية. - إذا كان العنصر مساويًا للهدف، عد بفهرسه فورًا.
- إذا انتهت الحلقة دون تطابق، عد بـ
-1.
English
public class Main {
public static void main(String[] args) {
int[] a = {4, 8, 15, 16, 23};
int target = 15;
int found = -1;
for (int i = 0; i < a.length; i++) {
if (a[i] == target) {
found = i;
break; // stop early, we have it
}
}
System.out.println(found); // 2
}
}
ما سرعة البحث الخطي؟
- في أسوأ الحالات (القيمة في آخر المصفوفة أو غير موجودة)، فإنه يفحص كل عنصر.
- بالنسبة لقائمة بها
nعناصر، يصل عدد الفحوصات القصوى إلىn. نطلق على هذا الوقت خطياً. - للمصفوفات الصغيرة، هذا مناسب تمامًا. أما للمصفوفات المرتبة الكبيرة جدًا، يمكننا أن نفعل أفضل.
البحث الثنائي يتطلب مصفوفة مرتبة
- البحث الثنائي لا يعمل إلا عندما تكون المصفوفة مرتبة بالفعل (من الصغير إلى الكبير).
- يفحص العنصر الوسطى، ثم يتخلص من نصف المصفوفة في كل خطوة.
- هذا أسرع بكثير: مليون عنصر يحتاج حوالي 20 فحصًا، وليس مليونًا.
فكرة البحث الثنائي
- احتفظ بحددين:
low(البداية) وhigh(النهاية). - انظر إلى الفهرس الوسطى
mid = (low + high) / 2. - إذا كان
a[mid]مساويًا للهدف، عد بـmid. - إذا كانت
a[mid]صغيرة جداً، يجب أن يكون الهدف على اليمين، لذا اضبطlow = mid + 1. - إذا كان
a[mid]كبيرًا جدًا، يجب أن يكون الهدف على اليسار، لذا اضبطhigh = mid - 1. - توقف عندما يتجاوز
lowhigh؛ حينها القيمة غير موجودة، عد بـ-1.
English
public class Main {
public static void main(String[] args) {
int[] a = {2, 5, 8, 12, 16, 23, 38}; // sorted!
int target = 16;
int low = 0;
int high = a.length - 1;
int found = -1;
while (low <= high) {
int mid = (low + high) / 2;
if (a[mid] == target) {
found = mid;
break;
} else if (a[mid] < target) {
low = mid + 1; // go right
} else {
high = mid - 1; // go left
}
}
System.out.println(found); // 4
}
}
عندما تكون القيمة غير موجودة
- كلا البحثين يُرجعان
-1عندما لا يكون الهدف موجوداً في المصفوفة. - بالنسبة للبحث الثنائي، تنتهي الحلقة عندما تتقاطع
low > high— الحدود قد تداخلت، فلا يوجد ما يتبقى للبحث عنه. - تعامل دائمًا مع حالة
-1في الكود الذي يستدعي البحث.
English
public class Main {
public static void main(String[] args) {
int[] a = {2, 5, 8, 12}; // sorted
int target = 7; // not in the array
int low = 0;
int high = a.length - 1;
int found = -1;
while (low <= high) {
int mid = (low + high) / 2;
if (a[mid] == target) {
found = mid;
break;
} else if (a[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
System.out.println(found); // -1
}
}
أخطاء شائعة
- البحث الثنائي يتطلب مصفوفة مرتبة.
- البحث الخطي O(n)؛ الثنائي O(log n).
الآن جرب بنفسك
- كل مهمة تملأ هيكل الفئة مسبقاً — اكتب كودك داخل main، أو أكمل الدالة المعروضة.
- استخدم Check answer لترجمة كودك مع الاختبارات المرفقة وعرض النتائج. ابقِ واجهات الفئة والطريقة كما هي موضحة في Starter.
- كودك يُعالج ويُشغل على الخادم، لذا حتى التشغيل الأول سريع.
استكشف
البحث الخطي مقابل الثنائي
البحث الثنائي يقلص النطاق بنصف كل خطوة — فحوصات أقل بكثير.
الصعوبة 3/5 · 200 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
أكمل linearSearch(int[] a, int target). أرجع الفهرس لأول عنصر يساوي target، أو -1 إذا لم يكن في المصفوفة. افحص العناصر من الفهرس 0 للأعلى.
اضغط تشغيل لرؤية المخرجات هنا.
الصعوبة 3/5 · 200 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
أكمل binarySearch(int[] a, int target) لمصفوفة مرتبة. استخدم حدود low/high وافحص المنتصف في كل خطوة. أرجع فهرس target، أو -1 إذا كان مفقودًا.
اضغط تشغيل لرؤية المخرجات هنا.
الصعوبة 3/5 · 200 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
أكمل countOccurrences(int[] a, int target) الذي يُرجع عدد مرات ظهور target في a (مسح خطي). أرجع 0 إذا لم يظهر أبدًا.
اضغط تشغيل لرؤية المخرجات هنا.