از طریق منوی جستجو مطلب مورد نظر خود در وبلاگ را به سرعت پیدا کنید
جستجوی باینری در JavaScriptSearching یکی از متداول ترین کارهایی است که در حوزه علوم کامپیوتر انجام می شود. الگوریتم‌ها و ساختارهای داده زیادی برای کارآمدتر کردن جستجو وجود دارد. در این مقاله به ایده پشت باینری جستجو و روش پیاده سازی آن در جاوا اسکریپت خواهیم پرداخت. جستجوی دودویی بسیار ساده است، …
سرفصلهای مطلب
معرفی
جستجو یکی از رایج ترین کارهایی است که در حوزه علوم کامپیوتر انجام می شود. الگوریتم‌ها و ساختارهای داده زیادی برای کارآمدتر کردن جستجو وجود دارد.
در این مقاله، به ایده پشت آن نگاه می کنیم جستجوی باینری و روش پیاده سازی آن در جاوا اسکریپت.
جستجوی باینری یک الگوریتم جستجوی بسیار ساده، بصری و در عین حال کارآمد است. تنها هشدار این است که فقط آرایه های مرتب شده را کار می کند، بنابراین برخی از پیش پردازش ها روی داده های ما به منظور مرتب سازی ممکن است لازم باشد.
درک جستجوی باینری
جستجوی باینری یک است تفرقه بینداز و حکومت کن الگوریتمی که هر بار بررسی می‌کند که آیا عنصری از آرایه همان عنصری است که ما به دنبال آن هستیم، آرایه را تقریباً به نصف تقسیم می‌کند.
به عبارت دیگر، ما مسئله را به مسائل ساده‌تر تقسیم می‌کنیم تا زمانی که به اندازه کافی ساده شود که بتوان آنها را مستقیماً حل کرد. بیایید فرض کنیم یک آرایه مرتب شده (به ترتیب صعودی) داریم و به مراحل جستجوی باینری نگاهی بیندازیم:
- عنصر میانی آرایه داده شده را پیدا کنید.
- عنصر میانی را با مقداری که به دنبال آن هستیم مقایسه کنید کلید).
- اگر کلید کمتر از عنصر وسط است، در نیمه سمت چپ جستجو کنید.
- اگر کلید بیشتر از عنصر میانی است، در نیمه سمت راست جستجو کنید.
- اگر کلید برابر با عنصر میانی است، شاخص عنصر میانی را برگردانید.
- مراحل 1، 2 را ادامه دهید تا زمانی که یک عنصر واحد باقی بماند.
- اگر کلید هنوز پیدا نشد، -1 را برگردانید.
برای درک بهتر این موضوع، اجازه دهید به مثالی نگاه کنیم که چرا هر بار که یک عنصر را بررسی می کنیم، می توانیم به سادگی نیمی از محدوده جستجوی فعلی را کنار بگذاریم:
مشابه این تقسیم اول، می‌توانیم به تقسیم آرایه ادامه دهیم تا زمانی که عنصر را پیدا کنیم، یا در نهایت فقط یک نامزد برای کلید داشته باشیم.
در این مورد، ما تنها با یک نامزد احتمالی برای کلید مواجه شدیم و مشخص شد که با عنصر مورد نظر ما مطابقت دارد.
همانطور که در مثال می بینید، مقایسه های نسبتا کمی برای یافتن عنصر مورد نیاز ما انجام شد. یعنی، ما فقط نیاز به انجام چهار مقایسه برای یافتن عنصر در آرایه ای از 11 عنصر داشتیم. بعداً نگاهی دقیق‌تر به کارایی جستجوی باینری خواهیم داشت، اما از قبل باید مشخص باشد که از الگوریتم‌های جستجوی ساده مانند جستجوی خطی برتری می‌یابد.
پیاده سازی جستجوی باینری در جاوا اسکریپت
اکنون که منطق پشت جستجوی باینری را بررسی کردیم، اجازه دهید آن را در جاوا اسکریپت پیاده سازی کنیم:
function binarySearch(sortedArray, key){
let start = 0;
let end = sortedArray.length - 1;
while (start <= end) {
let middle = Math.floor((start + end) / 2);
if (sortedArray(middle) === key) {
// found the key
return middle;
} else if (sortedArray(middle) < key) {
// continue searching to the right
start = middle + 1;
} else {
// search searching to the left
end = middle - 1;
}
}
// key wasn't found
return -1;
}
در اینجا، ما از دو متغیر برای پیگیری وضعیت استفاده می کنیم start و end از زیرآرایه فعلی که در حال جستجو هستیم. عنصر میانی را پیدا می کنیم و سپس بررسی می کنیم که آیا مساوی، کوچکتر یا بزرگتر از آن است key.
همانطور که قبلا توضیح داده شد، با توجه به اینکه ما یک آرایه مرتب شده داریم، می توانیم نیمی از عناصر آرایه را کنار بگذاریم. ما این کار را در کد با تغییر کد انجام می دهیم start یا end متغیر، بسته به روی جایی که ما به جستجوی خود ادامه می دهیم. اگر عنصر فعلی که به آن نگاه می کنیم کمتر از کلید باشد، تغییر می دهیم start به middle + 1 و به طور موثر عنصر فعلی و همه عناصر کمتر از آن را کنار بگذارید.
کارایی جستجوی باینری
پیچیدگی زمانی جستجوی باینری است O(log2ن)، جایی که n تعداد عناصر آرایه است. این در مقایسه با جستجوی خطی که دارای پیچیدگی زمانی است، بسیار بهتر است بر). مانند بسیاری از الگوریتم های جستجوی دیگر، جستجوی باینری یک الگوریتم است درجا الگوریتم یعنی مستقیما کار می کند روی آرایه اصلی بدون ایجاد هیچ کپی.
با این حال باید در نظر داشته باشیم که جستجوی باینری فقط کار می کند روی آرایه های مرتب شده خود مرحله مرتب‌سازی، در صورت استفاده از یک الگوریتم مرتب‌سازی کارآمد، دارای پیچیدگی است O(nlogn). این بدان معنی است که در بیشتر موارد، اگر آرایه کوچک است، یا اگر فقط یک بار نیاز به جستجو در آن داشته باشیم، a بی رحمانه الگوریتم (به عنوان مثال جستجوی خطی) ممکن است بهتر باشد.
با توجه به این موضوع، جستجوی باینری در زمانی که نیاز به جستجوی مکرر داریم واقعاً می درخشد روی آرایه های بزرگ همانطور که قبلا ذکر شد، ما فقط به 4 مقایسه نیاز داشتیم (مقایسه ها فشرده ترین وظایف همه الگوریتم های جستجو هستند)، برای یک آرایه از 11 عنصر. با این حال، اگر آرایه ای از 10000000 عنصر داشتیم، فقط باید بررسی کنیم 24 عناصر، به عنوان مثال 0.0002% از کل آرایه
نتیجه
در این مقاله نگاهی به جستجوی باینری انداخته ایم. منطق و پیاده سازی ساده، شهودی و کارآمد آن را به یک الگوریتم بسیار محبوب برای نشان دادن آن تبدیل کرده است تفرقه بینداز و حکومت کن استراتژی
منتشر شده در 1403-01-18 22:47:04
