Searching: linear and binary
طريقتان للبحث
- البحث يعني إيجاد أين تكون قيمة في مصفوفة (أو القول بأنها غير موجودة).
- البحث الخطي يفحص كل عنصر واحدًا تلو الآخر. يعمل على أي مصفوفة.
- البحث الثنائي أسرع بكثير لكنه يحتاج إلى أن تكون المصفوفة مرتبة أولاً.
البحث الخطي
- تجول من الفهرس
0إلىn - 1، مقارنًا كل عنصر بالهدف. - رُجع الفهرس لحظة العثور عليه. إذا وصلت للنهاية، رُجع
-1. - لمصفوفة من
nعناصر، هذا يفحص حتىnمنها.
لماذا الترتيب يمكّن البحث الثنائي
- إذا كانت المصفوفة مرتبة، يمكنك القفز إلى الوسط والمقارنة.
- إذا كان الوسط صغيرًا جدًا، يجب أن يكون الهدف في النصف الأيمن؛ إذا كبيرًا جدًا، في النصف الأيسر.
- كل خطوة تتخلص من نصف المصفوفة، لذا فهي سريعة جدًا (حوالي
log2(n)خطوات).
low, high, mid
- احتفظ بحدَين:
low(البداية) وhigh(النهاية). الوسط هوmid = low + (high - low) / 2. - إذا كان
a[mid]هو الهدف، رُجعmid. إذا كانa[mid] < target، حرّكlow = mid + 1؛ وإلاhigh = mid - 1. - توقف عندما
low > high— الهدف غير موجود، لذا رُجع-1.
#include <stdio.h>
int main(void) {
int a[] = {1, 3, 5, 7, 9}; // sorted!
int target = 7, lo = 0, hi = 4, found = -1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] == target) { found = mid; break; }
if (a[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
printf("%d\n", found); // 3
return 0;
}
أخطاء شائعة
- البحث الثنائي يتطلب مصفوفة مرتبة.
- البحث الخطي يفحص كل عنصر بالتتابع.
الآن جرب بنفسك
- للبحث الثنائي، افترض أن المصفوفة مرتبة مسبقًا. استخدم
low،high، وmid. - أعد
-1عندما لا يتم العثور على القيمة. لا تكتبmain— المتحقق يوفر واحدًا.
البحث الخطي مقابل الثنائي
Binary search halves the range each step.
الصعوبة 3/5 · 200 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
Complete int linear_search(const int a[], int n, int target) so it returns the index of the first target, or -1 if it is not in the array. Do ليس write a main.
اضغط تشغيل لرؤية المخرجات هنا.
الصعوبة 3/5 · 200 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
Complete int binary_search(const int a[], int n, int target) for a sorted array. Return the index of target, or -1. Use low, high, and mid. Do ليس write a main.
اضغط تشغيل لرؤية المخرجات هنا.
الصعوبة 3/5 · 200 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
Complete int first_negative(const int a[], int n) so it returns the index of the first item less than 0, or -1 if there is none. Do ليس write a main.
اضغط تشغيل لرؤية المخرجات هنا.