جستجوی خطی

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

روش تکرار

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

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

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

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