الگوریتم جستجوی سه گانه (Ternary Search)

  • شنبه ۱۱ آبان ۱۳۹۸
  • بازدید ۳۶ نفر

ternary search algorithm 7307 تصویر

الگوریتم جستجوی سه گانه (Ternary Search)

در این بخش الگوریتم جستجوی سه گانه (Ternary Search) را بررسی خواهیم کرد. این الگوریتم مانند الگوریتم Binary Search است با این تقاوت که آرایه به سه قسمت تقسیم می کند و دو مقدار را به عنوان مقادیر وسط در نظر میگیرد. از آنجا که در مرحله یک آرایه به سه آرایه تقسیم می شود، زمانی جستجو نیز کاهش می یابد.

ternary search algorithm 7307 1 تصویر

مسئله

با توجه به آرایه مرتب داده شده (arr[])، تابعی بنویسید که عنصر x را در آرایه جستجو کند.

ورودی – خروجی

مثال

پیاده سازی الگوریتم جستجوی سه گانه با زبان سی پلاس پلاس:

امتحان کنید

خروجی:

نکات

  • پیچیدگی زمانی این الگوریتم برابر با O(log3 n) است.
  • فضای موقت برابر با O(1) است.
ثبت نظر
ریفریش کنید!
نظرات کاربران (۰ مورد)

هیچ نظری ثبت نشده است