بدیهی است که در پروژه های کوچک خود و یا حتی یک سیستم بسیار پیچیده محاسبه قیمت خودرو به دنبال عنصری از آرایه ها و یا مقادیر از پیش تعﯿﯿن شده باشیم ، برای جستجو میان این داده ها و استفاده از آن ها میتوانیم از انواع الگوریتم استفاده کنیم کهاین الگوریتم ها شامل جستوجوی خطی، جستجوی باینری و جستجوی درون یابی میباشد. همچنین نوع دیگری از جستجو داده ها به نام جدول در هم سازی (هَش تِیبل) وجود دارد که داده ها را به روشی مرتبط با هم ذخیره سازی میکند . در این مقاله سعی داریم انواع الگوریتم های جستجو نام برده شده در بالا را به همراه توضیح و کاربرد آن ها را به شما شرح دهیم .
بدیهی است که در پروژه های کوچک خود و یا حتی یک سیستم بسیار پیچیده محاسبه قیمت خودرو به دنبال عنصری از آرایه ها و یا مقادیر از پیش تعﯿﯿن شده باشیم ، برای جستجو میان این داده ها و استفاده از آن ها میتوانیم از انواع الگوریتم استفاده کنیم که این الگوریتم ها شامل جستوجوی خطی، جستجوی باینری و جستجوی درو ن یابی میباشد. همچنین نوع دیگری از جستجو داده ها به نام جدول در هم سازی (هَش تِیبل) وجود دارد که داده ها را به روشی مرتبط با هم ذخیره سازی میکند . در این مقاله سعی داریم انواع الگوریتم های جستجو نام برده شده در بالا را به همراه توضیح و کاربرد آن ها را به شما شرح دهیم .
جستجوی خطی از ساده ترین الگوریتم های جستجو است و استفاده از آن بسیار ساده است . در این نوع الگوریتم جستجو ، یک جستجو ترتیبی بر روی تمامی عناصر موجود در داده ها صورت میگیرد ، یعنی هر عنصر بررسی میشود و در صورت وجود مطابقت با آیتم و یا داده تعﯿﯿن شده این عنصر خاص بازگشت داده میشود و اگر یافت نشود به جستجو خود ادامه میدهد تا به انتهای لیست داده ها برسد.
مثال : را در آرایه جستجو کند. x با توجه به آرایه داده شد ه تابعی بنویسید که عنصر
arr = {90 , 50 , 300 , 900 , 100 , 69 , 85}
x = 69
جواب :
ابتدا از سمت چپ آرایه شروع میکنیم و دونه به دونه عناصر را با مقدار x مقایسه میکنیم سپس اگر
با x و اما اگر مقدار (return) با یکی از عناصر آرایه مطابقت داشته باشد ، اندیس آن را باز میگردانیم x مقدار
- هیچ کدام از داده های آرایه هم خوانی نداشت مقدار 1 را باز میگردانیم .
#include <iostream>
using namespace std;
int search(int arr[], int n, int x) {
int i;
for (i = 0; i < n; i++)
if (arr[i] == x)
return i;
return -1;
}
int main(void) {
int arr[] = {
90,
50,
300,
900,
100,
69,
85
};
int x = 69;
int n = sizeof(arr) / sizeof(arr[0]);
int result = search(arr, n, x);
(result == -1) ? cout << "Element is not present in array": cout << "Element is present at index " << result;
return 0;
}
خروجی شما باید این باشید : Element is present at index 5
بدین ترتیب توانستیم با استفاده از جستجوی خطی عنصر مورد نیاز را از آرایه بدست آوریم .
جستجو دودویی یا همان باینری ، الگوریتمی است که برای پیدا کردن یک مقدار عددی از میان آرایه ای مرتب به کار میرود و به این شکل کار میکند که در ابتدا عنصر مورد نظر شما را با خانه وسط آرایه مقایسه میکند ، اگر مقدار با مقدار وارد شما یکی بود جستجو تمام میشود و آن را برمیگرداند در غیر این صورت اگر مقدار شما از مقدار خانه وسط آرایه بزرگ تر بود جستجو در قسمت بالایی آرایه و اگر کوچک تر بود در قسمت پاﻳﻴنی آرایه به همان شکل انجام میشود تا به مقدار مورد نظر برسد و آن را برگرداند و در غیر این صورت مقدار 1- را برمیگرداند.
مثال : با توجه به آرایه تابعی بنویسید که عنصر x را در آرایه جستجو کند.
arr = {2 , 3 , 4 , 10 , 40}
x = 10
جواب : پیاده سازی الگوریتم دودویی به دو شکل ممکن است (بازگشتی و حلقه) که هر دو آن ها را برای شما پیاده سازی میکنیم
تابع بازگشتی :
int binary(int arr[], int l, int r, int x) {
if (r >= l) {
int mid = l + (r - l) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binary(arr, l, mid - 1, x);
return binary(arr, mid + 1, r, x);
}
return -1;
}
int main(void) {
int arr[] = {
2,
3,
4,
10,
40
};
int n = sizeof(arr) / sizeof(arr[0]);
int x = 10;
int result = binary(arr, 0, n - 1, x);
(result == -1) ? printf("element is not present in array"): printf("element is present at index ",
result);
return 0;
}
روش حلقه :
int binary(int arr[], int l, int r, int x) {
while (l <= r) {
int m = l + (r - l) / 2;
if (arr[m] == x)
return m;
if (arr[m] < x)
l = m + 1;
else
r = m - 1;
}
return -1;
}
int main(void) {
int arr[] = {
2,
3,
4,
10,
40
};
int n = sizeof(arr) / sizeof(arr[0]);
int x = 10;
int result = binary(arr, 0, n - 1, x);
(result == -1) ? printf("element is not present in array"): printf("element is present at index ", result);
return 0;
}
خروجی که باید ببینید :
element is present at index 3
درواقع الگوریتم جستوجوی درون یابی نسخه پیشرفته و بهبود یافته جستجوی دودویی یا همان باینری میباشید . عملکرد این الگوریتم را با یک مثال توضیح میدهیم ، فرض کنید که در یک داده طولانی از اسم افراد نیازی دارید نام "حسین" را پیدا کنید طبیعتا منطقی نیست که از جستجوی دودویی به دلیل زمان بالای جستجو آن استفاده کنیم ، جستجوی درون یابی اینجا به کمک ما میاید و جستجو را از عناصری که با "ح" شروع شده اند آغاز میکند تا مقدار ورودی مارا پیدا کند و برگرداند.
مثال : با توجه به آرایه تابعی بنویسید که عنصر x را در آرایه جستجو کند
arr = {10, 12, 13, 16, 18, 19, 20, 21, 22, 23, 24, 33, 35, 42, 47}
x = 18
جواب : برای پیدا کردن موقعیتی که جستجو باید از آن شروع شود، از فرمول زیر استفاده می کنیم:
pos = lo + [ (x-arr[lo])*(hi-lo) / (arr[hi]-arr[Lo]) ]
int interpolationSearch(int arr[], int n, int x) {
int lo = 0, hi = (n - 1);
while (lo <= hi && x >= arr[lo] && x <= arr[hi]) {
if (lo == hi) {
if (arr[lo] == x) return lo;
return -1;
}
int pos = lo + (((double)(hi - lo) /
(arr[hi] - arr[lo])) * (x - arr[lo]));
if (arr[pos] == x)
return pos
if (arr[pos] < x)
lo = pos + 1;
else
hi = pos - 1;
}
return -1;
}
int main() {
int arr[] = {
10,
12,
13,
16,
18,
19,
20,
21,
22,
23,
24,
33,
35,
42,
47
};
int n = sizeof(arr) / sizeof(arr[0]);
int x = 18;
int index = interpolationSearch(arr, n, x);
if (index != -1)
cout << "element found at index " << index;
else
cout << "element not found."
return 0;
خروجی که باید ببینید:
element is present at index 4
جدول در هم ساز (Hash Table)
در ابتدا باید بگوییم که جدول درهم ساز (HashTable) چیست ، فرض کنید انبوهی از قطعه های کوچک بازی خانه سازی لِگو داریم ، در این بین نیاز دارید شکلی خاص را پیدا کنیم ، اگر بخواهیم از روش های قبلی استفاده کنیم برای این حجم از داده منطقی نیست و مدت زمان زیادی صرف پیدا کردن آیتم مورد نظر ما میشود. اینجاست که درهم سازی به ما کمک میکند تا دقیقا همان شکلی که دنبالش هستیم را به صورت مستقیم و جایی که هست پیدا کنیم. همچنین گفتنی است که به جدول درهم ساز Hashtable, Hashmap و Dictionary نیز میگویند.
اکنون بیاید راجب ساختار جدول درهم ساز یا همان Hash Table صحبت کنیم ، در Hash Table هر مقدار یا همان Value متصل و مربوط به یک کلید یا همان Key خاص میباشد. و همچنین هرگز نمیتوانیم دو کلید یکی داشته باشیم.
در Hash Table بین کلید و مقدار ها رابطه ای معنادار وجود دارد که توسط Hash Function و توسط عملیات ریاضی ، درست میشود .
هش فانکشن تابعی است یک طرفه که بهتر است یک به یک نیز باشد به این معنی که به ازای هر X تنها یک Y وجود دارد.
دلیل این که میگویید بهتر است یک به یک باشند این است که از تصادف یا همان Collision جلوگیری کنیم ، فرض کنید خروجی دو عملیات ریاضی در برنامه یکی باشند که به این معنی است که میبایست هردوی آن ها درون یک خانه از آرایه قرار بگیرد که باعث ایجاد مشکل میشود.
