الگوریتم و کد جستجوی دودویی (باینری)

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

جستجوی دودویی چگونه عمل میکند؟

قبل از هر چیز باید بگویم که برای استفاده از جستجوی دودویی آرایه باید به صورت صعودی (یا نزولی) مرتب شده باشد.ویژگی جستجوی دودیی این است که با هر بار مقایسه نیمی از عناصر بازه مشخص شده کنار گذاشته میشوند.فرض کنید که میخواهیم عدد x را در یک آرایه مرتب شده با استفاده از باینری سرچ پیدا کنیم،به صورت زیر عمل میکنیم

  1. x را با عنصر میانی آرایه مقایسه میکنیم.
  2. اگر با x برابر بود ایندکس آن خانه را برمیگردانیم.
  3. اگر از x کوچکتر بود نیمه سمت راست آرایه و در غیر این صورت نیمه سمت چپ آرایه را انتخاب میکنیم.
  4. سه مرحله بالا را برای نیمه انتخاب شده تا زمانی انجام میدهیم که عنصر مورد نظر در آرایه پیدا شود.
  5. اگه عنصر پیدا نشد مقدار -۱ را برمیگردانیم

کد جستجوی دودویی به زبان c++

 

کد جستجوی دودویی به زبان c++ (بازگشتی)

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

مرتبه زمانی
مرتبه زمانی جستجوی دودویی O(Log n) است و از فرمول T(n) = T(n/2) + c بدست می آید.