جستجوی خطی

یکی از الگوریتم‌هایی که برای جستجوی یک سری داده وجود دارد جستجوی ترتیبی (به انگلیسی: sequential search) یا جستجوی خطی (به انگلیسی: linear search)است. این الگوریتم کلیه عناصر درون یک لیست را یکی یکی بررسی می‌کند تا آرگومان جستجو پیدا شود.

این الگورتم جزو ساده‌ترین الگوریتم‌های جستجو می‌باشد. که حالت خاصی از جستجوی جامع (به انگلیسی: Brute-force search) می‌باشد.

مقدمه

یک الگوریتم جستجو به‌طور کلی الگوریتمی است که درون یک مجموعه از داده‌ها که توسط یک نوع ساختمان داده ذخیره شده‌اند؛ مکان یک مقدار داده شده به عنوان آرگومان جستجو را درون ساختمان داده مشخص می‌کند، یا تعیین می‌کند در مجموعه وجود دارد یا خیر.

شبه‌کد

روش تکرار

شبه کد به روش تکرار به صورت زیر است. در این روش مشاهده می‌شود که آرایه از ابتدا مورد بررسی قرار می‌گیرد و اگر داده مورد نظر یافت شد؛ محل آن داده در آرایه را بر می گرداند و در غیر اینصورت مقدار qرا بر می گرداند. در این روش معمولاً آرایه را از 0 تا n-1 یا از 1 تا n بررسی می‌کنند. .مقداردq زمانی بازگشت داده می‌شود که آرایه تا خانه ی n یا n-1 بررسی شده باشد و داده مورد نظر یافت نشده باشد.

 For each item in the list:
     if that item has the desired value,
         stop the search and return the item's location.
 Returnًq
 .

روش بازگشتی

و شبه کد به روش بازگشتی به صورت زیر است:

LinearSearch(value, list)
   if the list is empty, return Λ;
   else
     if the first item of the list has the desired value, return its location;
     else return LinearSearch(value, remainder of the list)

روش جستجو معکوس

در روش جستجو معکوس (به انگلیسی: Searching in reverse order) دو مقایسه انجام می‌شود. یکی برای اینکه ببینیم آیا آرایه به انتها رسیده‌است؟ و یکی برای اینکه ببینیم آیا داده مورد نظر درون آرایه موجود هست یا خیر؟ و در نهایت دو مقدار برگشتی خواهیم داشت که اگر این مقدار فقط برابر n+1 بود؛ به معنای این است که داده یافت نشده است. این شبه کد را ببینید:

 Set i to 1.
 Repeat this loop:
     If i> n, then exit the loop.
     If A[i] = x, then exit the loop.
     Set i to i + 1.
 Return i.

و شبه کد زیر جستجو در جهت معکوس را بیان می‌کند که در این روش هم دو مقدار برگشتی خواهیم داشت. اگر این مقدار فقط برابر 0 بود؛ به معنای این است که داده یافت نشده است. این شبه کد را ببینید:

 Set i to n.
 Repeat this loop:
     If i ≤ 0, then exit the loop.
     If A[i] = x, then exit the loop.
     Set i to i − 1.
 Return i.

پیاده‌سازی با مثال

کد زیر به زبان ++C روش جسجوی خطی را نشان می‌دهد. مقدار x درون آرایه A با n عنصر جستجو می‌شود و موقعیت آن را بر می گرداند. اگر در آرایه وجود نداشته باشد صفر برگردانده می‌شود.

  int i=0;
  for(i=0;i<=n;i++)
  {
     if(a[i] == x)
     {
        cout<<"find!";
        return 1;
     }
     else if(a[i]!= x)
     contiue;
  }
  cout<<"Not Found!";
  return 0;

پیچیدگی

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

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

جستارهای وابسته

الگوریتم جستجوی دودویی

الگوریتم جستجو

منابع

• مشارکت‌کنندگان ویکی‌پدیا. «Sequential Search». در دانشنامهٔ ویکی‌پدیای انگلیسی.

• Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein