از طریق منوی جستجو مطلب مورد نظر خود در وبلاگ را به سرعت پیدا کنید
جستجوی خطی در JavaScriptSearching، در زمینه علوم کامپیوتر، عبارت است از process قرار دادن یک عنصر خاص در لیست/آرایه داده شده. اگر دقت کنیم، می توانیم الگوریتم های جستجو را در همه جا پیدا کنیم. در نظر بگیرید process ورود به یک وب سایت ایمیل و رمز عبور وارد شده با جفت‌های کلید-مقدار موجود جستجو می‌شوند…
سرفصلهای مطلب
معرفی
جستجو، در زمینه علوم کامپیوتر، موضوع است process قرار دادن یک عنصر خاص در لیست/آرایه داده شده. اگر دقت کنیم، می توانیم الگوریتم های جستجو را در همه جا پیدا کنیم.
در نظر بگیرید process ورود به یک وب سایت ایمیل و رمز عبور وارد شده با جفت‌های کلید-مقدار موجود در پایگاه داده جستجو می‌شوند تا اعتبار کاربر را تأیید کنند.
در این مقاله، اجازه دهید به اساسی ترین الگوریتم برای جستجو در لیست معینی از عناصر نگاه کنیم – جستجوی خطی.
درک جستجوی خطی
الگوریتم جستجوی خطی مجموعه ای از دستورالعمل ها برای پیمایش لیست داده شده و بررسی هر عنصر در لیست است تا زمانی که عنصر مورد نظر خود را پیدا کنیم. اصطلاح فنی برای عنصر مورد نظر ما این است – کلید.
الگوریتم از سمت چپ ترین عنصر (یا شروع کننده) می رود و به جستجو ادامه می دهد تا اینکه یا عنصر مورد نظر را پیدا کند یا از تمام عناصر موجود در لیست عبور کند.
اگر عنصر پیدا شد، موقعیت (یا index) عنصر. اگر عنصر مورد نظر ما در لیست وجود نداشته باشد، به طور کلی برمی گردیم -1.
پیاده سازی جستجوی خطی در جاوا اسکریپت
می توانیم با استفاده از a از لیست داده شده عبور کنیم for حلقه بیایید به اجرای جستجوی خطی نگاه کنیم:
function linearSearch(arr, key){
for(let i = 0; i < arr.length; i++){
if(arr(i) === key){
return i
}
}
return -1
}
در اینجا ما تمام عناصر موجود در یک آرایه را مرور می کنیم و هر عنصر را با کلید مقایسه می کنیم. اگر مطابقت پیدا کنیم، اندیس عنصر را برمی گردانیم. در مورد ما، متغیر i محل قرارگیری ما در آرایه را پیگیری می کند و اگر مطابقت پیدا کنیم، مقدار فعلی را برای آن برمی گردانیم i.
در صورتی که عنصر در لیست ما وجود نداشته باشد، linearSearch تابع هیچ کدام را بر نمی گرداند i مقدار از حلقه ما فقط return -1 بعد از حلقه نشان می دهد که تابع عنصر مورد نظر را پیدا نکرده است.
جستجوی خطی جهانی
در پیاده سازی قبلی، پس از برخورد با اولین رخداد عنصر مورد نظر، مقداری را برمی گردانیم (key). اما اگر بخواهیم شاخص های تمام رخدادهای یک عنصر معین را بررسی کنیم، چه؟
اینجاست که جستجوی خطی سراسری وارد می‌شود. این نوعی از جستجوی خطی است که در آن ما به دنبال چندین رخداد یک عنصر معین هستیم.
بیایید به اجرای جستجوی خطی جهانی نگاه کنیم:
function globalLinearSearch(arr, key){
let results = ()
for(let i = 0; i < arr.length; i++){
if(arr(i) === key){
results.push(i)
}
}
// If results array is empty, return -1
if(!results){
return -1
}
return results
}
در این حالت، به جای اینکه فوراً نمایه عنصر تطبیق را برگردانیم، آن را در یک آرایه ذخیره می کنیم. در پایان، آرایه شاخص ها را برمی گردانیم.
کارایی جستجوی خطی
جستجوی خطی یک مثال کلاسیک از a است بی رحمانه الگوریتم این بدان معناست که الگوریتم از هیچ منطقی استفاده نمی‌کند تا کاری را که قرار است به سرعت انجام دهد یا به نوعی دامنه عناصری را که در آن جستجو می‌کند کاهش دهد. key. هدف دیگر الگوریتم‌های جستجو این است که این کار را با نوعی پیش‌پردازش فهرست/آرایه، برای مثال مرتب‌سازی آن، کارآمدتر انجام دهند.
پیچیدگی زمانی جستجوی خطی است بر)، جایی که n تعداد عناصر موجود در لیستی است که ما در جستجوی آن هستیم. این به این دلیل است که ما همیشه هنگام محاسبه پیچیدگی زمانی، بدترین حالت را در نظر می گیریم. در مورد جستجوی خطی (مانند اکثر الگوریتم های جستجو) بدترین حالت زمانی رخ می دهد که عنصر در لیست وجود نداشته باشد. در این شرایط، ما باید همه چیز را طی کنیم n عناصر برای تعیین اینکه عنصر وجود ندارد.
نتیجه
در این مقاله، منطق پشت جستجوی خطی را دیدیم و سپس با استفاده از آن دانش، الگوریتم را در جاوا اسکریپت پیاده سازی کردیم. همچنین پیچیدگی زمانی الگوریتم جستجوی خطی را بررسی کرده‌ایم.
این الگوریتم جستجوی بسیار ساده است، الگوریتمی که از هیچ منطقی برای حذف محدوده خاصی برای جستجو یا با تمرکز استفاده نمی کند. روی سرعت.
منتشر شده در 1403-01-18 20:43:04
