در مورد جستجوی باینری و کاربرد آن در آردوینو صحبت کنید

1. مبانی جستجوی باینری

جستجوی باینری یک الگوریتم کارآمد برای یافتن یک مقدار خاص در یک آرایه مرتب شده است. ایده اصلی این است که به طور مکرر فاصله جستجو را به نصف تقسیم کنید.

مراحل الگوریتم:

با کل آرایه مرتب شده شروع کنید.

شاخص میانی آرایه را محاسبه کنید.

عنصر موجود در شاخص میانی را با مقدار هدف مقایسه کنید.

اگر عنصر میانی با هدف برابر باشد، جستجو موفقیت آمیز است.
اگر عنصر میانی بزرگتر از هدف باشد، هدف باید در نیمه پایینی آرایه باشد. بنابراین، جستجو در نیمه پایین ادامه دارد.
اگر عنصر میانی کمتر از هدف باشد، هدف باید در نیمه بالایی آرایه باشد. بنابراین، جستجو در نیمه بالایی ادامه دارد.

این مراحل را تا زمانی که هدف پیدا شود یا فاصله جستجو خالی شود، تکرار کنید.

مثال:

یک آرایه مرتب شده arr = را در نظر بگیرید [2, 4, 6, 8, 10, 12, 14, 16, 18, 20] و مقدار هدف 10 است.

ابتدا، شاخص میانی (0 + 9)/2 = 4 (تقسیم عدد صحیح) است. عنصر در شاخص 4 10 است که مقدار هدف است، بنابراین جستجو با موفقیت انجام می شود.

برنامه در آردوینو

ذخیره و بازیابی اطلاعات:

در آردوینو، ممکن است مجموعه‌ای از مقادیر کالیبراسیون سنسور مرتب شده داشته باشید. به عنوان مثال، اگر شما یک سنسور دما دارید و آن را در نقاط مختلف دمای شناخته شده کالیبره کرده اید. فرض کنید یک آرایه از جفت های ولتاژ – دما کالیبره شده دارید که بر اساس ولتاژ مرتب شده اند. هنگامی که ولتاژی را از سنسور می خوانید، می توانید از جستجوی دودویی برای یافتن سریع دمای مربوطه استفاده کنید.

مثال کد:

در اینجا یک مثال کد ساده در C/C++ (که در آردوینو استفاده می شود) برای انجام جستجوی باینری در یک آرایه آورده شده است.

cpp
// تابع جستجوی باینری
int binarySearch(int arr[]int l, int r, int x) {
در حالی که (l <= r) {
int mid = l + (r – l) / 2;
// بررسی کنید که x در اواسط وجود دارد یا خیر
اگر (arr[mid] == x)
اواسط بازگشت؛
// اگر x بزرگتر است، نیمه چپ را نادیده بگیرید
در غیر این صورت اگر (arr[mid] l = اواسط + 1;
// اگر x کوچکتر است، نیمه سمت راست را نادیده بگیرید
دیگر
r = اواسط – 1;
}
// اگر به اینجا برسیم، عنصر وجود نداشت
بازگشت -1;
}
// مثال استفاده
void setup() {
Serial.begin(9600);
int arr[] = {2، 4، 6، 8، 10، 12، 14، 16، 18، 20}؛
int n = sizeof(arr)/sizeof(arr[0])
int x = 10;
int result = باینری جستجو (arr, 0, n – 1, x);
اگر (نتیجه == -1)
Serial.println(“عنصر پیدا نشد”);
دیگر
Serial.println(“عنصر یافت شده در فهرست: ” + رشته(نتیجه));
}
حلقه خالی() {}

در این مثال، تابع binarySearch یک آرایه آرایه، شاخص سمت چپ l، شاخص راست r و مقدار هدف x را می گیرد. تابع در صورت یافتن ایندکس مقدار هدف یا اگر یافت نشد -1 را برمی گرداند. در تابع setup، یک آرایه تعریف شده است و جستجوی باینری برای مقدار هدف x انجام می شود. سپس نتیجه در مانیتور سریال چاپ می شود.

پیمایش منو:

اگر یک سیستم منو در آردوینو با لیست مرتب شده از گزینه ها دارید (به عنوان مثال، حالت های مختلف عملکرد مانند “Mode 1″، “Mode 2″، “Mode 3″، و غیره، که بر اساس حروف الفبا یا عدد مرتب شده اند)، جستجوی باینری می تواند برای پیمایش سریع به یک گزینه خاص استفاده شود. کاربر یک عدد یا یک کلمه کلیدی را وارد می کند و الگوریتم جستجوی باینری می تواند گزینه منوی مربوطه را به شیوه ای کارآمد پیدا کند.

مدیریت منابع:

در پروژه پیچیده‌تر آردوینو با حافظه محدود، ممکن است فهرستی مرتب‌شده از بلوک‌های حافظه موجود داشته باشید. از جستجوی دودویی می توان برای یافتن سریع یک بلوک حافظه با اندازه مناسب برای یک کار جدید یا ذخیره سازی داده استفاده کرد و زمان جستجو را در مقایسه با جستجوی خطی کاهش داد.