جستجوی خطی

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

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

مقدمه

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

شبه‌کد

روش تکرار

شبه کد به روش تکرار به صورت زیر است. در این روش مشاهده می شود که آرایه از ابتدا مورد بررسی قرار می گیرد و اگر داده مورد نظر یافت شد؛ محل آن داده در آرایه را بر می گرداند و در غیر اینصورت مقدار Λ را بر می گرداند. در این روش معمولا آرایه را از 0 تا n-1 و یا از 1 تا n بررسی می کنند. .مقدار Λ زمانی بازگشت داده می شود که آرایه تا خانه ی 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 Λ.

روش بازگشتی

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

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