خوارزميات البحث

عشرون سؤالًا لمليون اسم

• دفتر هواتف يحتوي على مليون اسم. عند فحصها واحدًا تلو الآخر، ستحتاج إلى نصف مليون مقارنة تقريبًا قبل العثور على الاسم المطلوب.
• افتحها من المنتصف بدلاً من ذلك، حدد أي نصف يحتوي الاسم، وتجاهل النصف الآخر. كرر العملية. تصل إلى أي اسم في عشرين مقارنة.
• نصف مليون مقابل عشرين ليس توفيرًا بسيطًا؛ بل هو الفرق بين برنامج يعمل وبرنامج لا يمكن استخدامه. ويكلف هذا شيئًا واحدًا: القائمة يجب أن تكون مرتبة مسبقًا.
• هذه الدرس是关于 البحث الخطي والبحث الثنائي، وكيفية أداء كل منهما، وكيفية الاختيار بينهما.

البحث الخطي

FOR i ← 1 TO n
    IF A[i] = target THEN
        RETURN i
    ENDIF
NEXT i
RETURN -1                     // not found

• يبدأ من البداية، يقارن كل عنصر مع العنصر المستهدف، ويتوقف عند العثور على تطابق أو الوصول إلى النهاية.
• يعمل على أي قائمة، مرتبة أو غير مرتبة، وأي بنية يمكن المرور خلالها.
• أسوأ حالة: العنصر المستهدف هو الأخير أو غير موجود، لذا يتم مقارنة جميع $n$ عناصر، وهو $O(n)$. في المتوسط، حوالي النصف.

واحدًا تلو الآخر، من البداية

البحث الثنائي

low ← 1 ;  high ← n
WHILE low <= high DO
    mid ← (low + high) DIV 2
    IF A[mid] = target THEN
        RETURN mid
    ENDIF
    IF A[mid] < target THEN
        low ← mid + 1
    ELSE high ← mid - 1
ENDWHILE
RETURN -1

• يتطلب أن تكون البيانات مرتبة. قارن العنصر الأوسط مع العنصر المستهدف: إذا تطابق، توقف؛ إذا كان المستهدف أكبر، تجاهل النصف السفلي؛ وإلا تجاهل النصف العلوي.
• كل مقارنة تنصف النطاق المتبقي للبحث، لذا فإن عدد المقارنات هو $O(\log_2 n)$.
• لهذا السبب يحتاج مليون عنصر إلى حوالي عشرين مقارنة: $2^{20}$ هو مجرد أكثر من مليون.

مثال محلول: تتبع بحث ثنائي

الاختيار بينهما

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

مثال محلول: تبرير الاختيار

تكلفة الحفاظ على الملف مرتبًا

• البحث الثنائي متاح فقط على قائمة مرتبة، وهذا الترتيب ليس مجانيًا. السؤال الذي يطلب منك تبرير اختيارك هو يطلب منك تقدير تكلفته.
• إذا كانت البيانات تُبحث غالبًا وتُعدَّل نادرًا، رتّبها مرة واحدة وستكون كل searches لاحق $\log_2 n$. هذا هو الحال قاموس أو جدولlookup.
• إذا كانت البيانات تتغير باستمرار، يجب أن يحافظ كل إدخال على الترتيب، مما يكلف إزاحة العناصر اللاحقة. يمكن حينها أن يكون البحث الخطي على بيانات غير مرتبة هو الأقل تكلفة إجماليًا.
• الأرقام تجعل الحجة ملموسة: مليون سجل يحتاج حتى مليون مقارنة بشكل خطي، ولكن فقط 20 بالبحث الثنائي، لأن $2^{20} > 10^6$.
• لذلك تذكر الإجابة المصححة كلا الجانبين: مدى تكرار البحث، ومدى تكرار التغيير.

علامات ضائعة

لقد فهمت الأمر