الگوریتم جستجوی دودویی

مقدمه: الگوریتم جستجوی دودویی باینری چیه؟

قسمت قبل درباره‌ی آموزش الگوریتم صحبت کردیم. اگر قسمت قبلی رو هنوز ندیدید، حتما ببینید چون از مقدمات این ویدئو به حساب میاد و تقریبا صحبت ‌هایی که کردم، صحبت های مهمی هستن. برای دیدن ویدئوی قبلی اینجا کلیک کنید.

تصور کن یه عالمه داده مثل یه کتابخونه پر از کتاب داری و دنبال یه کتاب خاصی هستی. یه راهش اینه که یکی‌یکی قفسه‌ها رو بگردی تا کتاب مورد نظرت رو پیدا کنی؛ اینجوری کلی وقت و انرژی مصرف می‌کنی. اما یه راه هوشمندانه‌تر اینه که بدونی کتاب‌ها بر اساس حروف الفبا مرتب شدن و مستقیم به قفسه‌ای بری که فکر می‌کنی کتاب اونجاست. حالا فرض کن تو این قفسه هم از وسط شروع کنی و باز هم اون سمت قفسه‌ای که کتابت احتمالش بیشتره بری. این روش همون جستجوی دودویی یا باینری (Binary Search) است، یعنی به جای اینکه همه چیز رو دونه به دونه بررسی کنی، با نصف کردن لیست به سرعت هدفت رو پیدا می‌کنی.

آموزش برنامه نویسی پایتون

آموزش پایتون : دوره‌ی آموزش پایتون بهترین انتخاب برای دانشجویان مبتدی در برنامه‌نویسی است، زیرا پایت...

مشاهده دوره

جستجوی دودویی: قدم به قدم

حالا بیایم دقیق‌تر به روش کار این الگوریتم نگاه کنیم. فرض کن یه لیست مرتب شده از اعداد داریم. ما در هر مرحله از وسط لیست شروع می‌کنیم و عدد وسطی رو چک می‌کنیم که آیا همون عددی که دنبالش هستیم یا نه.

مراحل:

انتخاب عدد وسط: اول از همه عدد وسط لیست رو پیدا می‌کنیم. این عدد قراره توی هر مرحله نقطه مقایسه ما باشه.

مقایسه: اگه اون عدد، همون چیزی بود که دنبالش می‌گشتیم، کار تمومه. اگه عددی که دنبالشیم بزرگ‌تر از وسط لیسته، نیمه دوم رو انتخاب می‌کنیم و اگه کوچیک‌تر بود، می‌ریم سراغ نیمه اول.

تکرار: این روند رو تا جایی ادامه می‌دیم که یا به جواب برسیم یا مطمئن بشیم که عدد توی لیست نیست.

مثال ساده‌تر: پیدا کردن شماره در دفترچه تلفن

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

جستجوی دودویی یا باینری همین کار رو با اعداد یا داده‌های مرتب انجام میده، فقط به شکلی خیلی منظم و سریع.

کد جستجوی دودویی در زبان برنامه‌نویسی دارت

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

int binarySearch(List<int> arr, int target) {

  int low = 0;

  int high = arr.length - 1;

  while (low <= high) {
      
    int mid = (low + high) ~/ 2;

    if (arr[mid] == target) {

      return mid; // عنصر پیدا شده

    } else if (arr[mid] < target) {

      low = mid + 1; // جستجو در نیمه بالایی

    } else {

      high = mid - 1; // جستجو در نیمه پایینی
    }

  }

  return -1; // عنصر پیدا نشد
}

void main() {

  List<int> numbers = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19];

  int target = 7;

  int result = binarySearch(numbers, target);

  if (result != -1) {
      
    print("عنصر در ایندکس $result پیدا شد.");

  } else {
      
    print("عنصر پیدا نشد.");
    
  }
  
}

توضیحات کد:

ورودی‌ها: تابع binarySearch دو ورودی داره: لیست arr که از قبل مرتب شده و عدد target که همون چیزی است که دنبالشی.

خروجی: اگه عدد توی لیست پیدا بشه، ایندکس اون عدد رو برمی‌گردونه، اگه نباشه، مقدار -1 رو برمی‌گردونه که نشون میده عدد توی لیست نیست.

نحوه جستجو: همون‌طور که توی توضیح الگوریتم گفتیم، ما هر بار نقطه وسط لیست رو انتخاب می‌کنیم و بسته به اینکه عدد هدف بزرگ‌تر یا کوچک‌تر از عدد وسطه، به نیمه بالایی یا پایینی می‌ریم.

آموزش برنامه نویسی دارت

مقدمه زبان برنامه نویسی دارت در سال‌های اخیر رشد آهسته و پیوسته‌ای داشته؛ به همین خاطر این روزها این...

مشاهده دوره

بررسی پیچیدگی زمانی و کارآمدی

یکی از سوالات مهم در دنیای الگوریتم‌ها اینه که یه روش یا الگوریتم چقدر سریع کار می‌کنه. جستجوی دودویی با پیچیدگی زمانی O(logn) خیلی سریع عمل می‌کنه. یعنی حتی اگه یه لیست خیلی بزرگ داشته باشی، این الگوریتم به جای اینکه تک‌تک عناصر رو بررسی کنه، هر بار لیست رو نصف می‌کنه و به همین خاطر، سرعتش خیلی بیشتر از جستجوی خطی O(n) هست.

مثال ساده از پیچیدگی زمانی:

فرض کن یه لیست ۱۰۰۰ تایی داری. توی جستجوی خطی باید ممکنه هر ۱۰۰۰ عنصر رو چک کنی. ولی توی جستجوی دودویی:

بعد از اولین مقایسه، ۵۰۰ عنصر حذف میشه.
بعد از دومین مقایسه، ۲۵۰ تا باقی می‌مونه.
و همین‌طور ادامه می‌ده تا بالاخره به عدد مورد نظر برسی.
در واقع، تعداد بررسی‌های لازم توی جستجوی دودویی به شدت کمتر از جستجوی خطی هست.

کاربردهای جستجوی دودویی در دنیای واقعی

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

پیدا کردن یه محصول توی یه فروشگاه آنلاین: فرض کن توی یه سایت فروشگاهی دنبال یه محصول خاصی هستی که قیمت‌هاشون مرتب شده. سایت می‌تونه با جستجوی دودویی، محصولی با قیمت موردنظر رو به سرعت پیدا کنه.

سیستم‌های مدیریت فایل: توی سیستم‌های ذخیره‌سازی، وقتی می‌خوای یه فایل خاص رو پیدا کنی، اگه فایل‌ها مرتب شده باشن، سیستم می‌تونه از جستجوی دودویی برای جستجو استفاده کنه.

جستجو در دیتابیس‌ها: در خیلی از سیستم‌های دیتابیس، داده‌ها به صورت مرتب ذخیره میشن و برای جستجوی سریع، از جستجوی دودویی استفاده میشه.

مزایا و معایب الگوریتم جستجوی دودویی

مزایا:

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

کارایی در لیست‌های بزرگ: وقتی با حجم زیادی از داده‌ها سروکار داری، این الگوریتم یه انتخاب عالیه.

معایب:

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

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

مقایسه جستجوی دودویی و خطی

برای درک بهتر تفاوت بین جستجوی دودویی و جستجوی خطی، بیایم یه مقایسه انجام بدیم. در جستجوی خطی، ما یکی‌یکی عناصر لیست رو بررسی می‌کنیم. یعنی اگه لیستی ۱۰ تایی داشته باشیم و عدد مورد نظر توی آخرین عنصر باشه، باید همه ۱۰ عنصر رو نگاه کنیم.

اما توی جستجوی دودویی، با نصف کردن لیست، به جای بررسی ۱۰ تا، ممکنه فقط ۴ یا ۵ بار نیاز به بررسی باشه تا به عدد مورد نظر برسیم. این تفاوت به‌خصوص وقتی لیست بزرگ باشه، خیلی بیشتر خودش رو نشون میده.

نتیجه‌گیری

الگوریتم جستجوی دودویی (Binary Search) یکی از سریع‌ترین و کارآمدترین روش‌ها برای جستجو در لیست‌های مرتب شده‌ست. با استفاده از تقسیم مداوم لیست به دو نیمه، می‌تونه خیلی سریع داده‌ها رو پیدا کنه. این الگوریتم توی خیلی از سیستم‌ها و برنامه‌های روزمره مثل فروشگاه‌های آنلاین، سیستم‌های مدیریت فایل و دیتابیس‌ها کاربرد داره.

با توجه به اینکه پیچیدگی زمانی اون O(logn) هست، می‌تونیم بگیم که این الگوریتم توی جستجوهای بزرگ، سرعت فوق‌العاده‌ای داره و به‌خصوص برای مسائل با حجم زیاد داده‌ها یه راه‌حل عالی به حساب میاد.

اگه می‌خواید الگوریتم جستجوی دودویی رو خیلی راحت و به زبان ساده یاد بگیرید، حتماً ویدیوی جدیدم رو که توی یوتیوب و آپارات گذاشتم ببینید! توی این ویدیو با یه روش خیلی ساده و جذاب توضیح دادم که چطوری با جستجوی دودویی می‌تونید توی لیست‌ها دنبال چیزی بگردید و پیداش کنید. پس همین الان یه سر به کانال یوتیوب یا آپاراتم بزنید و ویدیو رو ببینید!

راستی، یادتون نره که حتماً پیج “نابغه‌ها” رو توی یوتیوب، اینستاگرام و بقیه شبکه‌های اجتماعی دنبال کنید تا اولین نفرایی باشید که از آموزش‌های جدید باخبر می‌شید! 🔔