البحث عن خوارزمية بحث ثنائية فعالة في لغة C

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

توفر مكتبة C القياسية std::binary_search في رأس ، ولكنها فقط ترجع قيمة منطقية. كما لاحظ السائل، قد يكون هذا محبطًا في المواقف التي تكون فيها سرعة البحث الثنائي مطلوبة ومن المعروف أنه تم فرز البيانات.

لحسن الحظ، هناك تطبيقات بديلة متاحة توفر الوظيفة المطلوبة. أحد الخيارات الشائعة هو استخدام خوارزمية مخصصة تستفيد من الوظائف std::lower_bound، أو std::upper_bound، أو std::equal_range. فيما يلي نسخة مبسطة من هذا التنفيذ:

template
Iter binary_find(Iter begin, Iter end, T val) {
    // Determine the lower bound using binary search
    Iter i = std::lower_bound(begin, end, val);

    // If the element is found, return the iterator to it
    if (i != end && !(val 
بدلاً من ذلك، يمكن استخدام std::set، والذي يضمن ترتيب العناصر ويوفر طريقة البحث التي تُرجع مُكرِّرًا إلى العنصر المطلوب. ومع ذلك، من المهم مراعاة ما إذا كانت المتطلبات متوافقة مع استخدام المجموعة، خاصة في الحالات التي يلزم فيها تخزين مثيلات متعددة لنفس العنصر.