در این فصل چه یاد میگیری#
فصلِ قبل گفت مرتب کردن گران است. این فصل میگوید چه چیزی میخرد: در n = 8,000، پرسشِ «هست یا نه؟» که با جستوجوی خطی بهطورِ متوسط ۴٬۰۰۰ گام میخواست، با ۱۳ گام جواب میگیرد. و بعد نقطهٔ سربهسر را حساب میکنیم: از q = 24 پرسش به بعد، یک بار مرتب کردن بهصرفه است.
ولی مهمترین بخشِ این فصل جدولش نیست. binary search مشهورترین الگوریتمی است که برنامهنویسها غلط مینویسند — و بدترین شکلِ غلط نوشتنش هیچ خطایی نمیدهد. نسخهای که اینجا میبینی برای ۴۸۹ عضو از ۱٬۰۰۰ عضوی که واقعاً در فهرست هستند میگوید «پیدا نشد» و آبی از آب تکان نمیخورد.

آخر این فصل میتوانی:
binary searchرا با ناوردای بازه بنویسی و مرزهایش را توجیه کنی- خطای یکیکمیکیزیاد را با آزمونِ کامل پیدا کنی، نه با نگاه کردن
bisectرا درست بهکار ببری- نقطهٔ سربهسرِ «مرتب کردن در برابرِ جستوجوی خطی» را برای
nِ خودت حساب کنی
قبل از شروع#
از ترمِ ۳ فصلِ ۱: جستوجوی خطی و هزینهاش.
از فصلِ ۴: شمارشِ مقایسههای merge sort — بخشِ ۶ برای حسابِ نقطهٔ سربهسر به همان عدد احتیاج دارد و کدش اینجا فشرده تکرار میشود.
| اجرا | زمانِ تقریبی |
|---|---|
| CPU (پیشفرضِ Colab) | کمتر از یک دقیقه |
📓 نوتبوک: نوتبوک این فصل را در Colab باز کن — همهٔ کدهای این فصل آماده و بهترتیب داخلش هست.
۱. هفت عضو، با دست#
ایده در یک جمله: وسط را نگاه کن. اگر جوابت نبود، نصفِ بیفایده را دور بریز.
def binary_search_traced(values, target):
"""اندیسِ target یا -1، با چاپِ بازه در هر گام."""
lo, hi = 0, len(values) - 1
step = 0
while lo <= hi:
step += 1
mid = (lo + hi) // 2
print(f"گام {step}: بازه [{lo}..{hi}] -> mid={mid} values[mid]={values[mid]}")
if values[mid] == target:
return mid
if values[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1
row = [10, 11, 13, 14, 18, 25, 29]
print("فهرستِ مرتب:", row)
print("دنبالِ 25 :", binary_search_traced(row, 25))
print()
print("دنبالِ 12 :", binary_search_traced(row, 12))
فهرستِ مرتب: [10, 11, 13, 14, 18, 25, 29]
گام 1: بازه [0..6] -> mid=3 values[mid]=14
گام 2: بازه [4..6] -> mid=5 values[mid]=25
دنبالِ 25 : 5
گام 1: بازه [0..6] -> mid=3 values[mid]=14
گام 2: بازه [0..2] -> mid=1 values[mid]=11
گام 3: بازه [2..2] -> mid=2 values[mid]=13
دنبالِ 12 : -1
هفت عضو، حداکثر سه گام. و جستوجوی ناموفق هم سه گام خورد — چون تا وقتی بازه خالی نشود، هنوز جای امیدی هست.
ناوردای این حلقه یک جمله است و کلِ درستیِ الگوریتم روی آن سوار است: «اگر target در فهرست باشد، حتماً بینِ lo و hi است.» قبل از اولین دور درست است (بازه کلِ فهرست است) و هر دور هم درست میماند، چون فقط تکهای دور ریخته میشود که ثابت کردهایم نمیتواند شاملش باشد. وقتی بازه خالی شود، همان جمله میگوید target در فهرست نیست.
۲. گامها: log n در برابرِ n#
🤔 اول حدس بزن: با دو برابر شدنِ
n، بیشترین تعدادِ گامِbinary searchچند برابر میشود؟ و برای جستوجوی خطی؟ دو عدد بنویس، بعد جدول را ببین.
def binary_search(values, target):
"""(اندیس یا -1، تعدادِ گام)"""
lo, hi = 0, len(values) - 1
steps = 0
while lo <= hi:
steps += 1
mid = (lo + hi) // 2
if values[mid] == target:
return mid, steps
if values[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1, steps
def linear_search(values, target):
"""(اندیس یا -1، تعدادِ گام)"""
for i, v in enumerate(values):
if v == target:
return i, i + 1
return -1, len(values)
LADDER = [1_000, 2_000, 4_000, 8_000]
rows = {n: list(range(0, 2 * n, 2)) for n in LADDER}
def worst_steps(fn, values):
"""بیشترین گام روی همهٔ عضوهای موجود."""
return max(fn(values, v)[1] for v in values)
def average_steps(fn, values):
return sum(fn(values, v)[1] for v in values) / len(values)
print("جوابِ دو روش یکی است؟",
all(binary_search(rows[1_000], v)[0] == linear_search(rows[1_000], v)[0]
for v in rows[1_000]))
print("\n— binary search: بیشترین گام")
table([(n, worst_steps(binary_search, rows[n])) for n in LADDER], "گام", ",d")
print("\n— linear search: میانگینِ گام")
table([(n, average_steps(linear_search, rows[n])) for n in LADDER], "گام", ",.1f")
جوابِ دو روش یکی است؟ True
— binary search: بیشترین گام
n گام نسبت به سطر قبل
1,000 10 —
2,000 11 1.10
4,000 12 1.09
8,000 13 1.08
— linear search: میانگینِ گام
n گام نسبت به سطر قبل
1,000 500.5 —
2,000 1,000.5 2.00
4,000 2,000.5 2.00
8,000 4,000.5 2.00
10، 11، 12، 13 — هر دو برابر شدنِ n دقیقاً یک گام اضافه میکند. ستونِ نسبت 1.08 است و رو به یک. این O(log n) است و همان شکلی است که ترمِ ۱ فصلِ ۵ در تابعِ halve_down دید.
جدولِ دوم 2.00 است: O(n). و فاصلهٔ عملیشان را در سطرِ آخر ببین — 13 در برابرِ 4,000.
۳. دو مرز، دو شکستِ متفاوت#
حالا بدترین بخشِ این الگوریتم. مرزهای lo و hi سه جا نوشته میشوند — مقدارِ اولیه، شرطِ حلقه، و دو خطِ بهروزرسانی — و این سه باید با هم بخوانند. اگر نخوانند، دو اتفاق ممکن است بیفتد.
def search_bad_loud(values, target):
"""اشتباهِ اول: hi را برابرِ طول گرفتهایم، نه طول منهای یک."""
lo, hi = 0, len(values)
while lo <= hi:
mid = (lo + hi) // 2
if values[mid] == target:
return mid
if values[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1
try:
search_bad_loud([10, 11, 13, 14], 99)
except IndexError as err:
print(f"{type(err).__name__}: {err}")
IndexError: list index out of range
این یکی خوششانسی است. hi = len(values) یعنی بازه یک خانهٔ بیرونی هم دارد، و mid بالاخره روی همان خانه میافتد: IndexError. خطا صریح است و همانجا اصلاح میشود.
حالا نوعِ دوم:
def search_bad_quiet(values, target):
"""اشتباهِ دوم: شرطِ حلقه lo < hi است ولی بازه طوری کوچک میشود
که آخرین نامزد هیچوقت نگاه نمیشود."""
lo, hi = 0, len(values) - 1
while lo < hi:
mid = (lo + hi) // 2
if values[mid] == target:
return mid
if values[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1
sample = rows[1_000]
missed = [v for v in sample if search_bad_quiet(sample, v) == -1]
print("عضوهایی که وجود دارند ولی «پیدا نشد» گرفتند:", len(missed))
print("ده تای اول:", missed[:10])
print("هیچ خطایی داد؟ نه — فقط جوابِ غلط.")
عضوهایی که وجود دارند ولی «پیدا نشد» گرفتند: 489
ده تای اول: [2, 6, 10, 14, 18, 22, 26, 30, 34, 38]
هیچ خطایی داد؟ نه — فقط جوابِ غلط.
۴۸۹ عضو از ۱٬۰۰۰ عضوِ موجود، «پیدا نشد». یک نویسه اختلاف — <= به < — و هیچ استثنایی، هیچ هشداری، هیچ چیزی.
found = [v for v in sample if search_bad_quiet(sample, v) != -1]
print("درست جواب داد برای:", len(found), "عضو از", len(sample))
print("\nروی هشت عضو، دستی:")
tiny = [10, 11, 13, 14, 18, 25, 29, 31]
for v in tiny:
print(f" {v:>3} -> درست: {binary_search(tiny, v)[0]:>2}"
f" · معیوب: {search_bad_quiet(tiny, v):>2}")
درست جواب داد برای: 511 عضو از 1000
روی هشت عضو، دستی:
10 -> درست: 0 · معیوب: -1
11 -> درست: 1 · معیوب: 1
13 -> درست: 2 · معیوب: -1
14 -> درست: 3 · معیوب: 3
18 -> درست: 4 · معیوب: -1
25 -> درست: 5 · معیوب: 5
29 -> درست: 6 · معیوب: 6
31 -> درست: 7 · معیوب: -1
🔧 اگر کار نکرد: با
while lo < hi، حلقه وقتیloوhiبه هم برسند میایستد — بدونِ اینکه آن یک خانهٔ باقیمانده را نگاه کرده باشد. پس هر عضوی که جستوجو تا آخرین خانه دنبالش برود، «پیدا نشد» میگیرد.و راهِ گرفتنش هم در همین خروجی است: کلِ فهرست را آزمون کن. اگر فقط دو سه عدد را امتحان میکردی — مثلاً
11و14— کد سالم بهنظر میرسید. آزمونی که همهٔ عضوها را میسنجد یک خط بیشتر نیست و این ردهٔ خطا را کاملاً میگیرد.دو نسخهٔ سالم وجود دارد و باید یکیشان را انتخاب کنی و به آن وفادار بمانی: یا
hi = len - 1باwhile lo <= hiوhi = mid - 1، یاhi = lenباwhile lo < hiوhi = mid. قاطیِ این دو، همان چیزی است که اینجا دیدی.
۴. bisect: نسخهای که لازم نیست بنویسی#
پایتون این را در کتابخانهٔ استاندارد دارد و در کارِ واقعی همان را بهکار میبری. bisect_left اندیسِ جای درستِ یک مقدار را میدهد، نه اندیسِ خودش — پس برای پرسشِ «هست یا نه؟» یک بررسیِ کوچک هم لازم است.
from bisect import bisect_left, insort
haystack = [10, 11, 13, 14, 18, 25, 29]
def find(values, target):
"""جای درستِ استفاده از bisect برای پرسشِ «هست یا نه؟»"""
i = bisect_left(values, target)
if i < len(values) and values[i] == target:
return i
return -1
for target in (25, 12, 10, 29, 40):
print(f"find({target:>2}) = {find(haystack, target):>2}"
f" · binary_search = {binary_search(haystack, target)[0]:>2}")
fresh = []
for v in [29, 10, 14, 37, 13]:
insort(fresh, v)
print("\nساختنِ فهرستِ مرتب با insort:", fresh)
find(25) = 5 · binary_search = 5
find(12) = -1 · binary_search = -1
find(10) = 0 · binary_search = 0
find(29) = 6 · binary_search = 6
find(40) = -1 · binary_search = -1
ساختنِ فهرستِ مرتب با insort: [10, 13, 14, 29, 37]
bisect دقیقاً همان جوابها را میدهد — و سه سطرِ آخر نشان میدهد که مرزها را هم درست میگیرد: هم عضوِ اول، هم عضوِ آخر، هم مقداری بزرگتر از همه.
و insort چیزی است که در بخشِ ۶ به آن برمیگردیم: یک عضوِ تازه را در جای درستش درج میکند. پیدا کردنِ جا O(log n) است، ولی خودِ درج O(n) — چون list باید همه را جابهجا کند، همانطور که ترمِ ۲ فصلِ ۴ اندازه گرفت.
۵. پیششرط، و چیزی که نقضش میکند#
scrambled = [29, 10, 14, 37, 13, 25, 11, 18]
print("فهرستِ بیترتیب:", scrambled)
missed = [v for v in scrambled if binary_search(scrambled, v)[0] == -1]
print("عضوهایی که پیدا نشدند:", len(missed), "از", len(scrambled))
print("کدامها:", missed)
فهرستِ بیترتیب: [29, 10, 14, 37, 13, 25, 11, 18]
عضوهایی که پیدا نشدند: 5 از 8
کدامها: [29, 13, 25, 11, 18]
پنج عضو از هشت عضوِ موجود گم شدند، با کدِ کاملاً سالم. چون ناوردای بخشِ ۱ روی یک فرض ایستاده بود: «تکهای که دور میریزم نمیتواند شاملش باشد». روی فهرستِ بیترتیب این فرض دروغ است و کلِ استدلال فرو میریزد.
⚠️ مواظب باش: این ردهٔ خطا در کدِ واقعی معمولاً وقتی پیدا میشود که کسی جایی به فهرست عضو اضافه کرده و مرتببودنش را نگه نداشته.
binary searchهیچ راهی ندارد که بفهمد ورودیاش مرتب نیست — بررسی کردنش خودشO(n)است و کلِ صرفهجویی را از بین میبرد. پس مرتببودن یک قرارداد است که کدِ دیگری باید نگهش دارد، و در بازبینیِ کد باید صریح دنبالش بگردی.
۶. مرتب کردن چقدر خرج دارد و از کجا بهصرفه میشود#
حالا سؤالِ مهندسیِ فصل: یک بار مرتب کردن گران است. از چند پرسش به بعد جبران میشود؟
def merge_sort_comparisons(values):
"""merge sort فصلِ ۴، فقط برای شمردنِ هزینهٔ مرتبکردن."""
comparisons = 0
def go(vals):
nonlocal comparisons
if len(vals) <= 1:
return vals
mid = len(vals) // 2
left, right = go(vals[:mid]), go(vals[mid:])
out = []
i = j = 0
while i < len(left) and j < len(right):
comparisons += 1
if left[i] <= right[j]:
out.append(left[i])
i += 1
else:
out.append(right[j])
j += 1
out.extend(left[i:])
out.extend(right[j:])
return out
go(list(values))
return comparisons
rng = random.Random(SEED)
N = 8_000
pool = rng.sample(range(10 * N), N)
sort_cost = merge_sort_comparisons(pool)
in_order = sorted(pool)
targets = [rng.choice(in_order) for _ in range(200)]
per_linear = sum(linear_search(pool, t)[1] for t in targets) / len(targets)
per_binary = sum(binary_search(in_order, t)[1] for t in targets) / len(targets)
print(f"n = {N:,}")
print(f" هزینهٔ یک بار مرتب کردن : {sort_cost:>9,} مقایسه")
print(f" هر جستوجوی خطی : {per_linear:>9,.1f} گام")
print(f" هر binary search : {per_binary:>9,.1f} گام")
n = 8,000
هزینهٔ یک بار مرتب کردن : 93,580 مقایسه
هر جستوجوی خطی : 3,997.2 گام
هر binary search : 12.0 گام
print(f"{'q':>8}{'خطی':>16}{'مرتب + binary':>22}{'برنده':>20}")
for q in (1, 5, 10, 20, 25, 50, 100):
plain = q * per_linear
smart = sort_cost + q * per_binary
print(f"{q:>8,}{plain:>16,.0f}{smart:>22,.0f}"
f"{('خطی' if plain < smart else 'مرتب + binary'):>20}")
break_even = 1
while break_even * per_linear < sort_cost + break_even * per_binary:
break_even += 1
print("\nنقطهٔ سربهسر: از q =", break_even, "به بعد، مرتب کردن بهصرفه است.")
q خطی مرتب + binary برنده
1 3,997 93,592 خطی
5 19,986 93,640 خطی
10 39,972 93,700 خطی
20 79,945 93,821 خطی
25 99,931 93,881 مرتب + binary
50 199,862 94,182 مرتب + binary
100 399,723 94,783 مرتب + binary
نقطهٔ سربهسر: از q = 24 به بعد، مرتب کردن بهصرفه است.
بیستوچهار پرسش. برای یک فهرستِ هشتهزارتایی، اگر بیشتر از بیستوچهار بار قرار است در آن بگردی، مرتب کردن بهصرفه است — و اگر کمتر، یک حلقهٔ سادهٔ خطی کارِ درست است.
این همان نقطهٔ تقاطعِ ترمِ ۱ فصلِ ۹ است، این بار با q بهجای n. و مثلِ آنجا، عددش به مسئلهٔ خودت بند است، نه به الگوریتم: با بزرگتر شدنِ n هم هزینهٔ مرتب کردن بالا میرود و هم سودِ هر جستوجو، و این عدد آرامآرام جابهجا میشود.
✅ چک کن:
Nرا به1_000تغییر بده و کلِ بخشِ ۶ را دوباره بگیر. نقطهٔ سربهسر باید کمی پایین بیاید و نزدیکِ19دربیاید — چون با کوچک شدنِnهم هزینهٔ مرتب کردن پایین میآید و هم سودِ هر جستوجو. اگر عددت اصلاً تکان نخورد، احتمالاًin_orderرا بهروز نکردهای وbinary searchروی فهرستِ قدیمی میگردد.
📏 اندازه بگیر: چه چیزی با چه چیزی مقایسه شد؟ جستوجوی خطی روی فهرستِ بیترتیب در برابرِ
binary searchروی همان داده پس از مرتب شدن، با جوابِ تأییدشدهٔ برابر — و هزینهٔ مرتب کردن با همان واحد (مقایسه) شمرده شد تا جمع کردنشان معنا داشته باشد. در کدام بازهٔn؟ ۱٬۰۰۰ تا ۸٬۰۰۰ برای جدولِ گام، وn = 8,000با ۲۰۰ پرسشِ نمونه برای نقطهٔ سربهسر. با چند تکرار، و کمینه یا میانگین؟ یک اجرا؛ همهچیزِ این فصل شمارش است و قطعی، و پرسشهای نمونه هم باSEEDثابتاند.
🤖 از دستیارت بپرس: «چرا
binary searchروی فهرستِ نامرتب خطا نمیدهد ولی جوابِ غلط میدهد؟» بعد این را هم بپرس: «دو نسخهٔ سالمِ نوشتنِ مرزها را بنویس و بگو چرا نمیشود قاطیشان کرد.» — جوابِ درست باید هر دو را کامل بنویسد. اگر فقط یکی را داد، از او بخواه نسخهٔ دیگر را هم بنویسد و روی همهٔ عضوهای یک فهرستِ هزارتایی آزمونش کند.
واژههای تازهٔ این فصل#
| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
binary search |
باینری سرچ | یافتن با نصف کردنِ پیاپیِ بازهٔ جستوجو |
| off-by-one | آفبایوان | خطای یکیکمیکیزیاد در مرز یا شرطِ حلقه |
bisect |
بایسکت | ماژولِ استانداردِ پایتون برای جستوجو و درج در فهرستِ مرتب |
| break-even point | بریکایوِن پوینت | تعدادِ پرسشی که از آن به بعد سرمایهگذاریِ اولیه جبران میشود |
تمرینها
اول خودت فکر کن یا امتحان کن — بعد اینجا را باز کن.
در فصل بعد#
سه الگوریتمِ مرتبسازی نوشتیم و در کارِ واقعی هیچکدامشان را نمینویسی — sorted را صدا میزنی. فصلِ بعد میگوید چرا، و جوابش آن چیزی نیست که فکر میکنی.
مقایسههای sorted را میشماریم: در n = 80,000 عددِ 1,201,201 درمیآید و merge sort ما 1,203,739 — تقریباً یکی. یعنی الگوریتمش بهتر نیست. با این حال روی همان داده حدودِ سیزده برابر سریعتر است.
و یک کارِ دیگر هم میکند که ما بلد نبودیم: روی ورودیِ از پیش مرتب، همان 1,201,201 مقایسه به 79,999 میافتد و ستونِ نسبت 2.00 میشود.
به آخر این فصل رسیدی!
اگر ساختی و جواب داد، این دکمه مال توست.