تستخدم عمليات البحث للبحث عن عنصر ضمن قائمة من العناصر, ومن أشهر طرق البحث Linear search و Binary search
يتم البحث عن العنصر عن طريق المرور علي جميع العناصر حتي نصل الي العنصر المطلوب
ويمكن تنفيذ هذه الطريقة بالجافاسكريبت مثلا كالتالي
/**
* Search for an element in a list of elements using linear search
* if the element is found, it returns the index of the first match
* otherwise, it returns -1
*/
function linearSearch(list, element){
for(let key of list.keys()){
let item = list[key];
if(item === element){
// return the index of the first match
return key;
}
}
// if we don't find any match, return -1, because -1 is an invalid index
return -1;
}
كما تلاحظ, كلما زاد عدد عناصر القائمة زاد الوقت المطلوب لايداد العنصر لاننا نمر علي جميع العناصر
ولاننا نحسب أسوأ حالة فاننا سنأخذ الهنصر الاخير في الاعتبار, لنصل الي هذه العنصر نحتاج للمرور علي جميع العناصر, وكلما زاد عدد العناصر كلما زاد الوقت المطلوب للوصول الي هذا العنصر الاخير
اذا time complexity لهذه العملية هو O(n)
و space complixity هو O(1) لاننا لا نحتاج مساحة اضافية في الذاكرة لاجراء عملية البحث (لا نحتاج لتعريف متعيرات جديدة مثلا)
رغم بساطة هذه الطريقة الا انها ليست الاكثر كفاءة لاننا نحتاج المرور علي جميع العناصر, لذا نحتاج لالقاء نظرة علي binary search
في هذه الطريقة يتم ترتيب قائمة العناصر اولا ثم نقارن العنصر المطلوب ايجاده بالعنصر الذي في منتصف القائمة, وبناء علي ذلك نتحرك يمينا او يسارا, وبذلك نتخلص من نصف القائمة كل مرة
مثلا اذا كان لدينا قائمة تضم الارقام من 1 الي 10 ونريد البحث عن رقم 8, هنا منتصف القائمة الرقم 5
ولان العنصر المطلوب وهو 8 اكبر منه فاننا نحتاج التحرك يمينا (أي للقيم الاكبر) وبالتالي فان كل العناصر الاصغر من 5 يمكن التخلص منها
الان اصبح لدينا قائمة جديدة وهي الارقام من 6 الي 10 وتم التخلص من كل الارقام الاصغر من 6
منتصف القائمة الجديدة هو 8 وهو العنصر المطلوب
لاحظ اننا وجدنا العنصر المطلوب في خطوتين فقط وهو اسرع من طريقة linear search ولكن يحتاج لترتيب العناصر اولا