شارك المقالة
البحث الثنائي في Dart مع قائمة فارغة وقيم مكررة

البحث الثنائي في Dart مع قائمة فارغة وقيم مكررة

تنفيذ البحث الثنائي في Dart لقائمة أعداد مرتبة مع إرجاع أول تطابق، ومعالجة القائمة الفارغة والقيم غير الموجودة وفهم كلفة…

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

عقد الدالة قبل التنفيذ

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

حدود آمنة للقائمة الفارغة

المثال القديم كان يقرأ list[middle] قبل التأكد أن نطاق البحث غير فارغ، فيتعطل مع قائمة لا تحتوي عناصر. هنا نستخدم نطاقًا نصف مفتوح من low إلى high، حيث high يبدأ بطول القائمة. لا نقرأ منتصفًا إلا حين low أصغر من high، ويظل mid داخل الحدود. بعد انتهاء الحلقة نفحص أن low أقل من length قبل الوصول إلى العنصر. هذه الشروط مهمة أيضًا عندما تكون القيمة أصغر من كل العناصر أو أكبر منها، وليس في الحالة الفارغة فقط.

لماذا أول تطابق؟

إذا كانت قيمة المنتصف أصغر من المطلوب نتجاوزها وما قبلها، وإلا نضيق النهاية نحو اليسار. عند التساوي لا نتوقف فورًا لأن هناك احتمال وجود نسخة أسبق من القيمة. في النهاية نتحقق من التطابق عند الموضع المرشح. هذه سياسة lower-bound مبسطة للأعداد، وتختلف عن خوارزمية تعيد أي تطابق. إذا كنت تحتاج عدد النسخ أو آخر تطابق أو موضع إدراج فعرّف دالة وعقدًا واضحين لذلك بدل تغيير معنى الفهرس نفسه حسب الحالة.

الكلفة والفهرس الأصلي

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

النص والأعداد والمدخلات

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

اختبارات الحدود

اختبر صفر عنصر وعنصرًا واحدًا والتطابق عند البداية والنهاية وقيمة بين عنصرين وقيمًا مكررة. قارن نتائج الدالة مع indexOf على عدة قوائم مرتبة صغيرة في اختبار، وتحقق من عدم تغير المدخلات. لا تضف قراءة شبكة أو تصفية واجهة داخل حلقة البحث؛ أبقِ الخوارزمية مستقلة حتى يمكن اختبارها مباشرة. المثال لا يفترض أن كل بيانات API مرتبة، ويظل التحقق من عقد ترتيبها مسؤولية طبقة البيانات قبل استعماله في قائمة منتج أو نتائج بحث حقيقية.

مثال مستقل للتجربة

شغّل المثال داخل مشروع Flutter تجريبي. يعتمد على Material فقط ولا يحتاج assets أو أصنافًا من مشروع خاص. غيّر مساحة النافذة وجرّب تكبير النص أثناء الفحص، ثم انقل المكوّن إلى مشروعك بعد تحديد سياق قيوده الفعلي.

import 'package:flutter/material.dart';
void main() => runApp(const MaterialApp(home: DemoPage()));
int firstBinarySearch(List<int> sorted, int value) {
  var low = 0;
  var high = sorted.length;
  while (low < high) {
    final mid = low + (high - low) ~/ 2;
    if (sorted[mid] < value) { low = mid + 1; }
    else { high = mid; }
  }
  return low < sorted.length && sorted[low] == value ? low : -1;
}
class DemoPage extends StatefulWidget {
  const DemoPage({super.key});
  @override
  State<DemoPage> createState() => _DemoPageState();
}
class _DemoPageState extends State<DemoPage> {
  final _input = TextEditingController(text: '7');
  static const _data = [1, 3, 7, 7, 9, 12];
  String _result = 'Enter an integer';
  @override
  void dispose() { _input.dispose(); super.dispose(); }
  void _search() {
    final value = int.tryParse(_input.text.trim());
    setState(() {
      if (value == null) { _result = 'Invalid integer'; return; }
      final index = firstBinarySearch(_data, value);
      _result = index < 0 ? 'Not found' : 'First match index: $index';
    });
  }
  @override
  Widget build(BuildContext context) => Scaffold(
    appBar: AppBar(title: const Text('Binary search')),
    body: ListView(padding: const EdgeInsets.all(16), children: [
      Text('Sorted data: $_data'),
      TextField(controller: _input, keyboardType: const TextInputType.numberWithOptions(signed: true), decoration: const InputDecoration(labelText: 'Integer')),
      ElevatedButton(onPressed: _search, child: const Text('Search')),
      Text(_result),
    ]),
  );
}

مرجع الواجهة البرمجية

راجع التوثيق الرسمي لمطابقة السلوك مع إصدار Flutter المستخدم. نجاح المثال في مساحة واحدة لا يثبت توافق التصميم مع جميع الشاشات؛ اختبر حدود الانتقال والاتجاه واللغة والنص الطويل.

الصور والفيديو من الشرح السابق

الكود النصي أعلاه هو النسخة المصححة؛ قد تختلف المواد المرئية السابقة في أسماء المتغيرات أو طريقة التشغيل.

شرح كيفية استخدام binarySearch في Dart لتسهيل عملية البحث داخل list
شاهد أيضًا
مقالات ذات صلة
🚫 مانع الإعلانات مفعل

يجب إيقاف مانع الإعلانات لاستكمال تصفح الموقع