البحث والترتيب

البحث الخطي

البحث هو أن نجيب، إذا أُعطينا مجموعة وقيمة، هل القيمة موجودة وأين. ومن دون معلومات عن ترتيب البيانات، لا توجد استراتيجية غير النظر فيها واحدًا واحدًا: هذا هو البحث الخطي. وحين لا تكون القيمة موجودة، تُعيد هذه الدورة values.size()، أول موضع لا ينتمي إلى المتجه: فهو ليس فهرسًا صالحًا، فلا يُخلط بجواب، وهو الاصطلاح نفسه الذي تتّبعه المكتبة، كما سيُرى في القسم الخامس.

#include <cstddef>#include <print>#include <vector>​// الشرط المسبق: لا شيء.// الشرط اللاحق: تُعيد أصغر فهرس i يحقق values[i] == target،// أو values.size() إذا لم يكن target موجودًا.std::size_t linearSearch(const std::vector<int>& values, int target){    // اللامتغير: target ليس بين values[0], ..., values[i - 1].    for (std::size_t i{0}; i < values.size(); ++i) {        if (values[i] == target) {            return i;        }    }    return values.size();}​int main(){    const std::vector<int> codes{405, 112, 318, 207, 112, 530};    for (const int target : {207, 112, 999}) {        const std::size_t pos{linearSearch(codes, target)};        if (pos == codes.size()) {            std::println("{}: غير موجود", target);        } else {            std::println("{}: الموضع {}", target, pos);        }    }}

207: الموضع 3112: الموضع 1999: غير موجود

لامتغيّر السطر 10 يضمن الصحة. في البداية، حين يساوي i الصفر، يقرّر شيئًا عن جزء فارغ فيكون صحيحًا. وإذا صحّ عند بدء جولة ولم يكن values[i] هو المطلوب، صحّ عند انتهائها مع عنصر إضافي. غير أن للحلقة مخرجين: إذا نُفّذ return i; كان values[i] هو المطلوب، وبحكم اللامتغيّر لم يكن أي عنصر قبله كذلك، ومن ثمّ فإن i هو الظهور الأول (ولهذا يُبلَّغ عن 112، الذي يظهر مرتين، في الموضع 1)؛ وإذا انتهت الحلقة بالشرط، كان i مساويًا لـvalues.size()، ويقول اللامتغيّر إن القيمة غير موجودة في أي مكان. وتعليمة return داخل الحلقة تُنهي الدالة، ومعها الحلقة، وتغني عن عَلَم.

تُقاس الكلفة، بمعنى درس كلفة الخوارزمية، بالمقارنات values[i] == target. إذا لم تكن القيمة موجودة، تُجرى بالضبط $n$ مقارنة، واحدة لكل عنصر: هذه أسوأ حالة. وإذا كانت في الموضع $p$، تُجرى $p + 1$ مقارنة. فالبحث الخطي إذن من الرتبة $O(n)$: بضعف البيانات، ضعف العمل. ومن دون معلومات إضافية لا يمكن أن يُفعل أفضل من ذلك: فالخوارزمية التي تترك عنصرًا دون أن تنظر فيه لا تعرف هل كانت القيمة هناك.