{CodeGate}

جستجوی دودویی در جاوا (Binary Search)

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

  1. آشنایی با آرایه
  2. آشنایی با متد
  3. مرتب سازی
  4. الگوریتم بازگشتی

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

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

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

جست و جوی دودویی

پیاده جستجوی دودویی در جاوا

حال نوبت پیاده سازی رسیده است. برای پیاده سازی جستجوی دودویی در جاوا  اول نیاز داریم که خانه های آرایه ما sort باشد پس یک کلاس Sort مینویسیم که از مرتب سازی حبابی استفاده میکند.کد این کلاس به صورت زیر است:

بعد یک کلاس مینویسیم که جست و جوی دودویی ما درون آن باشد.اسم کلاس را Testbinarysearch میگذاریم. در این کلاس دو متد قرار دارد: 1. Main 2. Binarysearch. این کلاس ها از اسمشان کاربرشان معلوم است نیاز به توضیح اضافی ندارد!!! کد این کلاس به صورت زیر است:

کد جستجوی دودویی در جاوا به این صورت که ابتدا ما یک آرایه تعریف میکنیم و آرایه خود را مرتب میکنیم. بعد از مرتب کردن متد جستجوی دودویی در جاوا را صدا میزنیم تا عدد 5 را پیدا کند. در صورتی که پیدا شد اندیس آن خانه را در آرایه به برمیگرداند و اگر نبود 1- برمیگرداند.

در متد جستجوی دودویی در جاوا یک متغییر mid داریم که وسط آرای است. همانطوری که گفته شد ابتدا چک میکنیم که عددی به دنبال آن هستیم با خانه وسط یکی است یا خیر.

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

در غیر این صورت سمت چپ به دنبال آن میرویم.

قبل از هر کاری هم یک بررسی کوچک میکنیم ببینیم خانه ای برای جست و جو باقی مانده است یا نه!!!!

پسورد: www.codegate.ir

 

دسته : java, جاوا, حل مسائل با جاوا

دیدگاه بگذارید

۲ دیدگاه ها برای "جستجوی دودویی در جاوا (Binary Search)"

مطلع کردن شما از
avatar

مرتب کردن بر اساس:   جدیدترین | قدیمی ترین | بیشترین رای
مهندس
مهمان
مهندس
2 ماه های 16 روز های گذشته

میشه بگین خروجی برنامه چیه ممنون میشم 🙂

wpDiscuz