جستجوی باینری – انجمن DEV

جستجوی باینری چیست؟

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

مثالی از یک تابع جستجوی باینری در جاوا اسکریپت:

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) {
      return mid;
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return -1;
}

تابع binarySearch دو آرگومان می گیرد: آرایه ای که باید جستجو شود (arr) و مقدار هدفی که باید پیدا شود (هدف). دو اشاره گر چپ و راست را به ترتیب به ابتدا و انتهای آرایه مقدار دهی اولیه می کند.

سپس تابع وارد یک حلقه while می شود که تا زمانی که سمت چپ کمتر یا مساوی راست باشد ادامه می یابد. در هر تکرار، تابع شاخص نقطه میانی (وسط) فاصله جستجو را با استفاده از فرمول (چپ + راست) / 2 محاسبه می کند. سپس مقدار را در نقطه میانی با مقدار هدف مقایسه می کند.

اگر مقدار نقطه میانی با مقدار هدف برابر باشد، تابع شاخص نقطه میانی را برمی‌گرداند. اگر مقدار نقطه میانی کمتر از مقدار هدف باشد، تابع به‌روزرسانی می‌شود تا به mid + 1 برسد، و عملاً نیمه چپ فاصله جستجو را حذف می‌کند. اگر مقدار نقطه میانی بیشتر از مقدار هدف باشد، تابع دقیقاً تا وسط – 1 به‌روزرسانی می‌شود و عملاً نیمه سمت راست بازه جستجو را حذف می‌کند.

اگر تابع حلقه while را بدون یافتن مقدار هدف تکمیل کند، -1 را برمی‌گرداند تا نشان دهد که مقدار در آرایه یافت نشده است.

در اینجا مثالی از نحوه استفاده از تابع باینری جستجو آورده شده است:

const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
const target = 7;

const index = binarySearch(arr, target);
console.log(index); // Output: 6

چه زمانی از جستجوی باینری استفاده کنیم؟

جستجوی باینری یک الگوریتم بسیار کارآمد برای جستجو در یک آرایه یا لیست مرتب شده است. پیچیدگی زمانی O(log n) دارد که بسیار سریعتر از جستجوی خطی است (که پیچیدگی زمانی O(n) دارد).

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

جستجوی باینری زمانی موثرتر است که:

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

• داده ها ثابت یا تقریبا ثابت هستند: اگر داده ها دائما در حال تغییر هستند، جستجوی باینری ممکن است بهترین الگوریتم برای استفاده نباشد. هر بار که داده ها تغییر می کنند، فرآیند مرتب سازی باید تکرار شود که می تواند بسیار زمان بر باشد.

• اندازه داده بزرگ است: جستجوی باینری زمانی موثرتر است که مجموعه داده بزرگ باشد. اگر مجموعه داده کوچک باشد، هزینه سربار مرتب سازی داده ها و اجرای الگوریتم ممکن است ارزش مزایای عملکرد را نداشته باشد.

به طور خلاصه، جستجوی دودویی یک الگوریتم قدرتمند است که می تواند بهبود عملکرد قابل توجهی را در موقعیت های مناسب ارائه دهد. اگر نیاز به جستجو در یک مجموعه داده بزرگ دارید که ثابت یا تقریبا ثابت و مرتب شده است، جستجوی باینری گزینه بسیار خوبی برای بررسی است.