جستجوی خطی ساده ترین الگوریتم جستجو است. این کار با بررسی هر عنصر در لیست یک به یک ، از ابتدا شروع می شود ، تا زمانی که موردی را که به دنبال آن هستید پیدا کند.
کار جستجوی خطی
1 فرض کنید ما باید عنصر را پیدا کنیم k = 6 در زیر ذکر شده است.
2 از عنصر اول شروع کنید ، مقایسه کنید k با هر عنصر x.
3 اگر x == k، شاخص را برگردانید.
4 دیگر ، بازگشت not foundبشر
الگوریتم جستجوی خطی
LinearSearch(array, key)
for each item in the array
if item == value
return its index
کد جستجوی خطی
function linearSearch(arr, key){
for (let i = 0; i < arr.length; i++) if (arr[i] === key) return i
return "not found";
};
console.log(linearSearch([1, 2, 4, 5], 4));
پیچیدگی های جستجوی خطی
| پیچیدگی زمانی | |
|---|---|
| بهترین | o (1) |
| بدترین | o (n) |
| میانگین | o (n) |
| پیچیدگی فضا | o (1) |
| ثبات | n/a |
1. پیچیدگی های زمانی
-
بهترین مورد: O (1)
هنگامی که عنصر هدف اولین مورد در لیست است ، بلافاصله پیدا می شود. -
بدترین مورد: o (n)
هنگامی که هدف آخرین عنصر است یا اصلاً در لیست نیست. ما باید هر مورد را بررسی کنیم. -
مورد متوسط: o (n)
به طور متوسط ، هدف در جایی در وسط لیست قرار دارد ، بنابراین نیمی از عناصر بررسی می شوند.
2. پیچیدگی فضایی
-
پیچیدگی فضایی: O (1)
جستجوی خطی از فضای اضافی استفاده نمی کند ، فقط عناصر را یک به یک بررسی می کند.
برنامه های جستجوی خطی
1. داده های غیرقانونی
- جستجوی خطی به خوبی روی داده های بدون ساختار یا بدون ساختار کار می کند که مرتب سازی در آن امکان پذیر یا مورد نیاز نیست.
2 مجموعه داده های کوچک
- ایده آل برای لیست های کوچک که در آن عملکرد نگران کننده نیست.
3. جستجو در ورودی کاربر
- مورد استفاده در اعتبارسنجی ورودی اساسی که سیستم در لیستی از مقادیر مجاز یک مقدار را بررسی می کند.
4. جستجو در لیست های مرتبط
- از آنجا که لیست های پیوندی امکان دسترسی مستقیم توسط فهرست را ندارند ، جستجوی خطی مناسب است.
5. تاریخچه مرورگر یا جستجوی گپ
- به سرعت بررسی کنید که آیا URL یا پیام خاصی وجود دارد یا خیر.
6. یافتن ورودی های تکراری
- برای یافتن موارد مکرر ، از طریق هر عنصر بررسی کنید.
7. هدف آموزشی
- عالی برای آموزش مفاهیم جستجوی اساسی قبل از حرکت به الگوریتم های پیچیده تر مانند جستجوی باینری.
