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

کاهش و حل

در آرایه‌ی مرتب، هر بار عضو وسط بازه را با مقدار مورد جستجو مقایسه می‌کند و نیمی از بازه را کنار می‌گذارد.

جستجوی دودویی فقط روی آرایه‌ی مرتب کار می‌کند. بازه‌ی a[low..high] جایی است که target ممکن است باشد. در هر دور عضو وسط، a[mid]، را نگاه کن:

ادامه‌ی توضیح ↓

زمان: O(log n)
حافظه: O(1)
CLRS، بخش ۲.۳
جانسون‌باو، فصل ۷

ورودی:

n=10 · target=9خروجی PDF

ده عدد مرتب؛ ۹ بعد از سه بار نصف کردن بازه پیدا می‌شود.

def binary_search(a, target):
low = 0
high = len(a) - 1
while low <= high:
mid = (low + high) // 2
if a[mid] == target:
return mid
if a[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1

ناوردا: اگر target در آرایه باشد، در بازه‌ی a[low..high] است.

شروع اجرا

متغیرهای محلی

target9

نارنجی = در همین گام عوض شد

`a` list

13468911141720

Call stack

binary_search()خط 1

گام ۱ از ۱۷

رشد تعداد عملیات با اندازه‌ی ورودی

میانگین ۱۲ گراف تصادفی برای هر n (با seed ثابت). نشانگر توخالی = ورودی فعلی.

comparisons
probe
ورودی فعلی (n=10)

نمایش به شکل جدول

n	comparisons	probe
4	3.6	2.1
6	4.8	2.7
8	4.9	2.8
10	5.1	2.8
12	6.5	3.6
14	6	3.3
16	5.6	3.1

توضیح

ایده

اگر برابر target بود، پیدا شد.
اگر کوچک‌تر بود، target فقط می‌تواند در نیمه‌ی راست باشد: low = mid + 1.
اگر بزرگ‌تر بود، فقط در نیمه‌ی چپ: high = mid − 1.

وقتی low > high شد، بازه خالی است و target در آرایه نیست؛ تابع −1 برمی‌گرداند.

هزینه

هر دور اندازه‌ی بازه را نصف می‌کند، پس حداکثر ⌊log₂ n⌋ + 1 دور لازم است: برای هزار عضو حداکثر ۱۰ دور، برای یک میلیون عضو ۲۰ دور. حافظه‌ی اضافه O(1) است.

چرا آرایه باید مرتب باشد؟

کنار گذاشتن نیمی از بازه فقط وقتی درست است که بدانیم همه‌ی عضوهای سمت چپ a[mid] کوچک‌تر یا مساوی و همه‌ی عضوهای سمت راست بزرگ‌تر یا مساوی‌اند. اعتبارسنج ورودی آرایه‌ی نامرتب را قبول نمی‌کند.

در trace به چه چیزی نگاه کنی

نوار آبی بازه‌ی low..high است و خط چین آبی ارتفاع target را نشان می‌دهد.
فلش‌های low، mid و high زیر میله‌ها جابه‌جا می‌شوند؛ ببین بازه در هر دور نصف می‌شود.
ورودی «target تکراری» نشان می‌دهد که این نسخه لزوماً اولین تکرار را پیدا نمی‌کند.