Binary Search یعنی جستجوی عنصر در آرایه مرتب با تقسیم بازه به دو نیمه.
در این درس:
- طول آرایه (
n) و عناصر آن از ورودی برنامه گرفته میشوند - یک مقدار کلید (
key) برای جستجو دریافت میشود - آرایه باید مرتب باشد
- با تقسیم مداوم بازه موقعیت کلید پیدا میشود
در این درس:
-
آرایه با اندازه پویا (
new) ساخته میشود -
دو متغیر
lوrبازه فعلی را مشخص میکنند -
حلقهای تا زمانی که
l <= rادامه دارد:- اندیس وسط
midمحاسبه میشود - اگر عنصر وسط برابر کلید باشد → اندیس چاپ میشود
- اگر عنصر وسط کمتر از کلید باشد → بازه به نیمه راست منتقل میشود
- اگر بیشتر باشد → بازه به نیمه چپ منتقل میشود
- اندیس وسط
-
اگر کلید پیدا نشود،
-1چاپ میشود -
در پایان حافظه آرایه آزاد میشود (
delete[])
-
روش جستجوی سریع و کارآمد در آرایه مرتب
-
پیچیدگی زمانی: O(log n)
-
نیاز به آرایه مرتب دارد
-
تفاوت با Linear Search:
- تعداد مقایسهها بسیار کمتر است
- برای آرایههای بزرگ بسیار مناسبتر
./05_binary_search 5 10 20 30 40 50 30خروجی:
2
(عنصر 30 در اندیس ۲ قرار دارد)