جستجوی خطی (Linear Search) چیست؟ با Linear Search بیشتر آشنا شویم

در علوم کامپیوتر و ریاضیات، یک الگوریتم جستجو، الگوریتمی است که یک مسئله را به عنوان ورودی می‌گیرد و بعد از ارزیابی کردن راه حل‌های ممکن، یک راه حل برای آن مسئله برمی‌گرداند.

الگوریتم‌های جستجو، تکنیک‌هایی هستند که برای یافتن اطلاعات یا داده‌ها در میان مجموعه‌ای از داده‌ها استفاده می‌شوند.  در این مقاله ما به توضیح  جستجوی خطی می‌پردازیم و در مقالات آتی سعی خواهم کرد شما را با دیگر انواع جستجو آشنا کنم.

بصورت کلی، جستجوی خطی یکی از ساده‌ترین و ابتدایی‌ترین الگوریتم‌های جستجو است که در بسیاری از زبان‌های برنامه‌نویسی مورد استفاده قرار می‌گیرد.

این الگوریتم به‌خصوص برای مجموعه‌های داده کوچک یا زمانی که داده‌ها به‌صورت مرتب نیستند، بسیار مناسب است.

نحوه کارکرد جستجوی خطی

1. شروع از اولین عنصر: الگوریتم جستجو را از اولین عنصر آرایه شروع می‌کند.
2. مقایسه: هر عنصر را با مقدار مورد نظر مقایسه می‌کند.
3. ادامه تا پایان: اگر عنصر برابر با مقدار مورد نظر باشد، جستجو متوقف می‌شود و موقعیت آن عنصر برگردانده می‌شود. اگر به انتهای آرایه رسید و عنصر مورد نظر پیدا نشد، الگوریتم نتیجه را به‌عنوان "موجود نیست" برمی‌گرداند.

پیاده‌سازی جستجوی خطی در PHP

<?php
function linearSearch($array, $target) {
    for ($i = 0, $iMax = count($array); $i < $iMax; $i++) {
        if ($array[$i] === $target) {
                        return $i; 
        }
    }
    return -1; 
}

$numbers = [10, 20, 30, 40, 50];
$target = 30;

$result = linearSearch($numbers, $target);
if ($result != -1) {
        echo $result . 'Founded!';
} else {
        echo "Not found!";
}
?>

توضیح کد بالا:

1. تعریف تابع: تابع `linearSearch` دو پارامتر می‌گیرد: `$array` (آرایه‌ای که باید جستجو شود) و `$target` (عنصری که به دنبال آن هستیم).
  
2. پیمایش آرایه: از یک حلقه `for` برای پیمایش آرایه استفاده می‌شود. در هر تکرار، موقعیت کنونی `$i` را با مقدار مورد نظر (`$target`) مقایسه می‌کند.

3. مقایسه: اگر مقدار فعلی برابر با مقدار هدف باشد (`$array[$i] === $target`)، موقعیت آن عنصر (`$i`) برگردانده می‌شود.

4. عدم وجود عنصر: اگر حلقه به پایان برسد و عنصر پیدا نشود، `-1` به عنوان نشانه‌ای از عدم وجود عنصر برگردانده می‌شود.

5. نمونه استفاده: در قسمت پایانی کد، آرایه‌ای از اعداد ایجاد شده و یک مقدار هدف مشخص می‌شود. سپس تابع جستجوی خطی فراخوانی می‌شود و نتیجه آن چاپ می‌شود.

نکات مهم در مورد جستجوی خطی:

- پیچیدگی زمانی: جستجوی خطی در بدترین حالت پیچیدگی زمانی O(n) دارد، که به این معنی است که اگر n تعداد عناصر آرایه باشد، در بدترین حالت باید n بار مقایسه انجام شود.
- سادگی: این الگوریتم به خاطر سادگی‌اش درک و پیاده‌سازی آسان، اما برای داده‌های بزرگ کارایی مناسبی ندارد.

در ادامه به برخی نقاط قوت و نقاط ضعف این نوع جستجو اشاره میکنیم:

نقاط قوت جستجوی خطی

سادگی پیاده‌سازی: جستجوی خطی یک الگوریتم ساده  می باشد که  به راحتی قابل درک است. این سادگی باعث می‌شود که برای مبتدیان در برنامه‌نویسی و علوم رایانه انتخاب مناسبی باشد.

عدم نیاز به مرتب‌سازی داده‌ها: یکی از مزایای اصلی جستجوی خطی این هست که نیازی به مرتب‌سازی داده‌ها ندارد. این ویژگی آن را برای مجموعه‌های داده که به صورت تصادفی و بدون ترتیب خاصی هستند، مناسب می سازد.

عملکرد در مجموعه‌های کوچک: در صورت وجود مجموعه‌های داده کوچک، جستجوی خطی می‌تواند عملکرد مناسبی داشته باشد. زمان جستجو در این حالت معمولاً به اندازه کافی سریع است که برای بسیاری از برنامه‌ها قابل قبول باشد.

چالش‌ها و ضعف‌ها

کارایی پایین در مجموعه‌های بزرگ: جستجوی خطی دارای پیچیدگی زمانی O(n) است، که به این معنی است که زمان جستجو به طور خطی با افزایش تعداد عناصر در مجموعه داده‌ها افزایش می‌یابد. این عملکرد در مقایسه با الگوریتم‌های جستجوی پیشرفته‌تر (مانند جستجوی دودویی با O(log n)) می‌تواند بسیار کند باشد.

عدم بهره‌وری: در مقایسه با دیگر الگوریتم‌ها، جستجوی خطی بهینه‌ترین راه برای پیدا کردن داده‌ها نمی‌باشد، به خصوص زمانی که مجموعه داده‌ها بزرگ یا پیچیده باشد. چرا که این می‌تواند منجر به مصرف بالای زمان و منابع شود.

عدم استفاده از ساختارهای داده‌ای پیشرفته: جستجوی خطی نمی‌تواند از ویژگی‌های خاص ساختارهای داده‌ای پیشرفته‌تر مانند درخت‌ها یا جدول‌های هش  که می‌توانند جستجو را سریع‌تر و مؤثرتر کنند استفاده کند.

با توجه به توضیحات و نمونه کد بالا می توان نتیجه گرفت که جستجوی خطی یک الگوریتم مناسب برای جستجوی داده‌ها در مجموعه‌های کوچک و غیرمرتبه‌ای است. اما با توجه به ضعف‌های آن در مورد مجموعه‌های بزرگ و نیاز به کارایی بالا، بهتر است در مواقعی که مجموعه داده‌ها بزرگ و پیچیده هستند، از الگوریتم‌های جستجوی دیگر مانند جستجوی دودویی یا جستجوی هش استفاده کرد. انتخاب الگوریتم مناسب باید بر اساس نیازهای خاص برنامه و شرایط داده‌ها انجام شود.

اگر شما هم تجربه‌ای در استفاده از جستجوی خطی دارید یا سوالی در این زمینه دارید، خوشحال میشم از قسمت نظرات با ما در میون بذارید :)