از طریق منوی جستجو مطلب مورد نظر خود در وبلاگ را به سرعت پیدا کنید
سرفصلهای مطلب
وقتی صحبت از الگوریتم‌های جستجو می‌شود، اغلب به مظنونین معمولی مانند جستجوی باینری یا جستجوی خطی فکر می‌کنیم. اما وقتی فهرست‌های مرتب‌سازی‌شده و نامحدودی داریم که طول آن ناشناخته است یا تعیین آن آسان نیست، چه چیزی را باید انتخاب کنیم؟ جستجوی نمایی را وارد کنید، یک الگوریتم منحصر به فرد که دامنه جستجو را با هر مرحله دو برابر می کند و سرعت جستجو را افزایش می دهد. process مکان یابی یک عنصر خاص
در این مقاله کوتاه، به جزئیات این الگوریتم جالب، روش کارکرد آن و روش پیاده سازی آن با استفاده از جاوا اسکریپت خواهم پرداخت.
جستجوی نمایی چیست؟
جستجوی نمایی، همچنین به عنوان جستجوی مضاعف یا galloping شناخته می شود، الگوریتمی است که به ویژه برای جستجو در لیست های مرتب شده نامحدود یا بزرگ مفید است. با دوبرابر کردن دامنه جستجو کار می کند تا زمانی که محدوده ای را پیدا کند که احتمالاً مقدار مورد نظر در آن باشد. هنگامی که یک محدوده مناسب را محدود می کند، جستجوی باینری را در آن محدوده انجام می دهد تا عنصر دقیق را پیدا کند.
توجه داشته باشید: به خاطر داشته باشید که جستجوی نمایی برای کار موثر به یک آرایه مرتب شده نیاز دارد، زیرا از ماهیت مرتب شده داده ها برای محدود کردن سریع محدوده جستجو استفاده می کند.
پیاده سازی جستجوی نمایی در جاوا اسکریپت
در اینجا پیاده سازی گام به گام جستجوی نمایی در جاوا اسکریپت آمده است:
function exponentialSearch(arr, x) {
if (arr(0) === x) return 0;
// Find a range where the element might be present
let i = 1;
while (i < arr.length && arr(i) <= x) {
i = i * 2;
}
// Perform binary search within the found range
return binarySearch(arr, i / 2, Math.min(i, arr.length - 1), x);
}
function binarySearch(arr, left, right, x) {
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (arr(mid) === x) return mid;
if (arr(mid) < x) left = mid + 1;
else right = mid - 1;
}
return -1;
}
در اینجا روش عملکرد کد آمده است:
- اگر مقدار مورد نظر در اولین شاخص پیدا شود، 0 را برمی گرداند.
- در غیر این صورت، ایندکس را دو برابر می‌کند تا زمانی که محدوده‌ای را پیدا کند که ممکن است عنصر موجود باشد.
- سپس یک جستجوی باینری را در محدوده مشخص شده فراخوانی می کند.
اکنون می توانید تابع را با یک مثال آزمایش کنید:
let arr = (2, 3, 4, 10, 40);
let x = 10;
let result = exponentialSearch(arr, x);
console.log("Element found at index " + result);
پیچیدگی زمانی
پیچیدگی زمانی جستجوی نمایی است O(log i)، جایی که i موقعیت عنصر در آرایه است. این آن را به یک الگوریتم بسیار کارآمد برای آرایه های مرتب شده تبدیل می کند، به خصوص زمانی که طول آن ناشناخته است یا به راحتی تعیین نمی شود.
نتیجه
جستجوی نمایی یک الگوریتم قوی و کارآمد است که بهترین‌های جستجوی خطی و جستجوی دودویی را ترکیب می‌کند. با دو برابر کردن برد خود در هر مرحله، فضای جستجو را به سرعت محدود می کند و سپس یک جستجوی دودویی را برای تعیین دقیق عنصر هدف اعمال می کند. این ترکیب آن را به ویژه برای جستجو در لیست های مرتب شده بزرگ که طول آن از پیش تعیین نشده است مفید می کند.
منتشر شده در 1403-01-03 09:47:07
