الگوریتم جستجوی نمایی (Exponential Search)
در این بخش الگوریتم جستجوی نمایی (Exponential Search) را بررسی خواهیم کرد. روش کار این الگوریتم به این شکل است که ابتدا رنجی که ممکن است مقدار مورد نظر ما در آن باشد، پیدا می شود و سپس با استفاده از الگوریتم جستجوی باینری، آن رنج را جستجو می کنیم تا به عنصر مورد نظر برسیم.
Given a sorted array, and an element x to be
searched, find position of x in the array.
Input: arr[] = {10, 20, 40, 45, 55}
x = 45
Output: Element found at index 3
Input: arr[] = {10, 15, 25, 45, 55}
x = 15
Output: Element found at index 1
جستجوی نمایی شامل مراحل زیر است:
- پیدا کردن رنجی که عنصر مورد نظر در آن قرار دارد.
- انجام جستجوی باینری بر روی رنج پیدا شده.
چگونگه رنجی که عنصر مورد نظر ممکن است در آن باشد را پیدا کنیم؟
روش کار به این شکل است که ابتدا از یک زیر آرایه به طول ۱ شروع می کنیم و عنصر مورد نظر را با آخرین عنصر آن مقایسه می کنیم، سپس طول آرایه ۲، ۴ و … همینطور اضافه می شود تا زمانی که آخرین عنصر زیر آرایه از مقدار مورد جستجوی ما بزرگتر نباشد. زمانی که اندیس i را پیدا کردیم، می داینم که عنصر مورد نظر باید بین i/2 و i باشد.
پیاده سازی الگوریتم جستجوی نمایی با استفاده از زبان C++:
// C++ program to find an element x in a
// sorted array using Exponential search.
#include <bits/stdc++.h>
using namespace std;
int binarySearch(int arr[], int, int, int);
// Returns position of first occurrence of
// x in array
int exponentialSearch(int arr[], int n, int x)
{
// If x is present at firt location itself
if (arr[0] == x)
return 0;
// Find range for binary search by
// repeated doubling
int i = 1;
while (i < n && arr[i] <= x)
i = i*2;
// Call binary search for the found range.
return binarySearch(arr, i/2, min(i, n), x);
}
// A recursive binary search function. It returns
// location of x in given array arr[l..r] is
// present, otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l)
{
int mid = l + (r - l)/2;
// If the element is present at the middle
// itself
if (arr[mid] == x)
return mid;
// If element is smaller than mid, then it
// can only be present n left subarray
if (arr[mid] > x)
return binarySearch(arr, l, mid-1, x);
// Else the element can only be present
// in right subarray
return binarySearch(arr, mid+1, r, x);
}
// We reach here when element is not present
// in array
return -1;
}
// Driver code
int main(void)
{
int arr[] = {2, 3, 4, 10, 40};
int n = sizeof(arr)/ sizeof(arr[0]);
int x = 10;
int result = exponentialSearch(arr, n, x);
(result == -1)? printf("Element is not present in array")
: printf("Element is present at index %d",
result);
return 0;
}
امتحان کنید
خروجی:
Element is present at index 3
نکات
- پیچیدگی زمانی این الگوریتم برابر با O(Log n) است.
- فضای موقت در جستجوی باینری فوق برابر با O(Log n) زیرا به صورت بازگشتی پیاده سازی شده است. در صورتی که به صورت عادی پیاده سازی شود، برابر با O(1) خواهد بود.
کاربرد
- جستجوی نمایی برای جستجوهای محدود نشده، مثلا آرایه ای که اندازه آن نامحدود دارد، مفید است.
- جستجوی نمایی برای جستجو در آرایه های محدود و همچنین زمانی که عنصر مورد نظر به عنصر اول نزدیکتر باشد، بهتر از جستجوی باینری کار می کند.
نوشته الگوریتم جستجوی نمایی (Exponential Search) اولین بار در سورس سرا - آموزش برنامه نویسی. پدیدار شد.
