پیچیدگی زمان جستجوی باینری چیست؟

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

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

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

الگوریتم

• مرحله 1 - در مرحله اولیه ، اندازه Array ARR را به N ، 0 به پایین و N-1 به بالا اختصاص دهید. در اینجا ، 0 به اولین شاخص یا چپ ترین انتها اشاره دارد و N-1 به آخرین شاخص یا سمت راست ترین انتهای آرایه که جستجو می شود اشاره دارد.
• Step 2 - If low >آرایه بالا می تواند طولانی تر باشد. در این حالت ، -1 بازگردانده می شود تا نشان دهد که عنصر هدف در آرایه وجود ندارد.
• مرحله 3 - اگر کم باشد ، این بدان معنی است که ما آرایه را بین کم و زیاد به دو نیمه تقسیم می کنیم:
  • اولیه سازی اواسط = (کم + بالا) / 2 برای تقسیم آرایه به دو نیمه با arr [mid] به عنوان عنصر میانی آن
  • اگر عنصر هدف از عنصر میدلیموست بیشتر باشد ، زیر مجموعه سمت چپ عنصر میدلموست نادیده گرفته می شود. جستجو در زیر آرایه سمت راست عنصر Middlemost ادامه دارد ، با کم = میانی+1.
  • اگر عنصر هدف از عنصر Middlemost کوچکتر باشد ، این عنصر در زیر آرایه سمت چپ عنصر Middlemost با High = 1 جستجو می شود. زیر مجموعه راست نادیده گرفته می شود زیرا حاوی مقادیر بیشتر از عنصر میانی است.
  • این فرآیند تا زمانی که عنصر هدف پیدا شود تکرار می شود (Array ARR [MID] == عنصر هدف). بازگشت به طور مستقیم از اینجا نشان می دهد که میانی شاخصی است که در آن عنصر هدف در آرایه پیدا شده است.
  • اگر اندازه زیر آرایه 0 شود ، نتیجه می گیریم که عنصر هدف در آرایه وجود ندارد.

  در جستجوی یک عنصر موجود در آرایه:

  جستجوی عنصری که در آرایه وجود ندارد:

  تجزیه و تحلیل پیچیدگی جستجوی باینری

  • از آنجا که تجزیه و تحلیل با عنصر میانی شروع می شود ، در بهترین حالت ، ممکن است که عنصر میانی آرایه خود عنصر هدف باشد.
  • در غیر این صورت ، طول آرایه نصف می شود.
  • در تکرارهای زیر ، اندازه فرعی با استفاده از نتیجه مقایسه قبلی کاهش می یابد.
    • طول اولیه آرایه = n
    • تکرار 1 - طول آرایه = n/2
    • تکرار 2 - طول آرایه = (n/2)/2 = n/2^2^
    • تکرار k - طول آرایه = n/2^k^

    پس از تکرار K ، اندازه آرایه 1 می شود (به عنصر اول یا فقط عنصر آخر محدود می شود).

    Length of array = n/2^k^ = 1 => n = 2^k^ Applying log function on both sides: => log 2 (n) = log 2 (2^k^) => log 2 (n) = k log 2 2 = k =>K = ورود به سیستم

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

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

    بهترین سناریوی جستجوی باینری زمانی اتفاق می افتد که عنصر هدف در شاخص مرکزی باشد. در این شرایط ، فقط یک مقایسه وجود دارد. بنابراین ، بهترین پیچیدگی زمان جستجوی باینری o (1) است.

    میانگین پیچیدگی زمان مورد در جستجوی باینری

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

    بنابراین ، میانگین کل پیچیدگی زمان مورد در جستجوی باینری O (logn) است.

    بدترین حالت پیچیدگی زمان جستجوی باینری

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

    • در هر تکرار یا تماس بازگشتی ، جستجو به نیمی از آرایه کاهش می یابد.
    • بنابراین برای آرایه ای از اندازه n ، در حال ورود به سیستم است~2~n تکرار یا تماس های بازگشتی.

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

    تجزیه و تحلیل پیچیدگی فضایی جستجوی باینری

    در مورد رویکرد تکراری ، از فضای اضافی استفاده نمی شود. از این رو ، پیچیدگی فضا o (1) است.

    در بدترین حالت ، تماس های بازگشتی Logn در حافظه جمع می شوند.

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

    بنابراین ، در اجرای بازگشتی ، پیچیدگی کلی فضا o (logn) خواهد بود.