مبانی کامپیوتر و الگوریتم؛ از حل مسئله تا پروژهٔ عملی

در جست‌وجوی خطی، هر بار یک گزینه کنار می‌رود. اگر فهرست شمارهٔ کالاها مرتب باشد، می‌توان از یک مقایسه اطلاعات بیشتری گرفت: وقتی عدد وسط از هدف کوچک‌تر است، همهٔ عددهای سمت چپ آن هم کوچک‌ترند. جست‌وجوی دودویی همین اطلاعات حاصل از ترتیب را به کار می‌گیرد. موضوع اصلی این درس حفظ یک حلقه نیست؛ باید بدانیم کدام قسمت هنوز ممکن است پاسخ را داشته باشد و چرا حذف بقیه، جواب درست را از بین نمی‌برد.

پیش‌شرط را روشن بنویسید؛ مرتب بر اساس چه چیزی؟

قرارداد ما آرایه‌ای بدون خانهٔ خالی از عددهای صحیح امن است که به ترتیب صعودی مرتب شده؛ مقدارهای مساوی مجازند. هدف هم عدد صحیح امن است. نتیجه، شاخص یکی از رخدادهای هدف یا−1 برای نبودن آن است. از مرتب‌بودن بر اساس نام کالا نمی‌توان برای جست‌وجوی قیمت استفاده کرد. همین‌طور متن‌های «۲» و«۱۰» با عددهای۲ و۱۰ قرارداد یکسانی ندارند. پیش‌شرط نادرست ممکن است جواب ظاهراً معقول اما غلط بسازد؛ الگوریتم موظف نیست از ورودی نامرتب، ترتیب پنهانی اختراع کند.

برای جداکردن مسئولیت‌ها، یک مرحلهٔ آماده‌سازی داریم که نوع، محدوده و ترتیب را در یک عبور بررسی می‌کند و نسخه‌ای مستقل می‌سازد. سپس هستهٔ جست‌وجو چند بار روی همان نسخه اجرا می‌شود. در مثال آموزشی، Object.freeze از تغییر خانه‌های این آرایهٔ عددی جلوگیری می‌کند؛ موضوع کپی عمیق شیءها در اینجا مطرح نیست. اگر به‌جای عدد، محصول‌های تو‌در‌تو داشته باشیم، این حفاظت سطحی برای همهٔ فیلدها کافی نیست. #validation-contracts و قرارداد مالکیت داده را کنار هم ببینید.

یک قرارداد بازه انتخاب کنیم: [lo, hi)

در بازهٔ نیمه‌باز، lo داخل محدوده است وhi خارج از آن. بنابراین در آغازlo=0 وhi=طول داریم. بازه وقتی خالی است کهlo=hi شود؛ برای آرایهٔ خالی هم از ابتدا چنین است. شاخص وسط را با lo + floor((hi−lo)/2) می‌سازیم. مادامی کهlo<hi باشد، وسط شاخص معتبری در همان بازه است. نمادهای باز و بسته را فقط شکل ظاهری ندانید؛ شرط حلقه، تغییر مرزها و معنای خالی‌بودن همگی به این قرارداد وابسته‌اند.

binaryIndexPrepared(a, key):
    پیش‌شرط: a صعودی و مطابق قرارداد داده است
    lo ← 0
    hi ← طول a
    تا زمانی که lo < hi:
        mid ← lo + کف((hi - lo) / 2)
        اگر a[mid] < key: lo ← mid + 1
        وگرنه اگر a[mid] > key: hi ← mid
        وگرنه: برگردان mid
    برگردان -1

اگر مقدار وسط کوچک‌تر از هدف باشد، خود وسط هم پاسخ نیست؛ lo را بهmid+1 می‌بریم. اگر بزرگ‌تر باشد، وسط و سمت راستش حذف می‌شوند؛ چونhi بیرون بازه است، مقدار تازهٔhi خودmid می‌شود. در حالت برابری، شاخص را برمی‌گردانیم. هر شاخهٔ بدون پاسخ، اندازهٔ بازه را کم می‌کند. نوشتنlo=mid ممکن است در بازهٔ تک‌عضوی هیچ پیشرفتی ایجاد نکند؛ بسیاری از حلقه‌های بی‌پایانِ جست‌وجوی دودویی، خطای زبان نیستند، خطای تعریف بازه‌اند.

ردگیری موفق؛ هدف۳۱ در یک فهرست شش‌عضوی

آرایهٔ [۴،۹،۱۵،۲۳،۳۱،۴۶] را بگیرید. وسط اول شاخص۳ و مقدار۲۳ است، پس هدف اگر وجود داشته باشد در شاخص‌های۴ و۵ است. وسط بعدی شاخص۵ و مقدار۴۶ است؛ بنابراین فقط شاخص۴ می‌ماند. مقایسهٔ سوم۳۱ را پیدا می‌کند و شاخص۴ برمی‌گردد. پاسخ، مقدار۳۱ نیست؛ مکان آن است. این تفاوت در رابط کاربرد دارد، چون می‌توان از همان شاخص، اطلاعات ردیف مربوط را نمایش داد.

گام    lo    hi    mid    a[mid]    تصمیم
۰      0     6     3      23        lo = 4
۱      4     6     5      46        hi = 5
۲      4     5     4      31        خروجی 4

اگر هدف در نخستین عنصر میانی پیدا شود، همان یک دورِ حلقه کافی است. در کد این درس، یک بررسی عنصر میانی ممکن است شامل هر دو سنجشِ < و > باشد؛ پس شمار دورهای حلقه با شمار عملگرهای مقایسه یکی نیست. اگر وجود نداشته باشد، بازه در نهایت خالی می‌شود و−1 برمی‌گردد. این مقدار را با شاخص صفر یکی نگیرید: صفر یک جای معتبر است. نوشتن شرط if(index) برای تشخیص موفقیت غلط است، چون صفر در جاوااسکریپت به حالت نادرست تبدیل می‌شود. بررسی صریح index !== -1، قرارداد نتیجه را بیان می‌کند. در اینجا #strict-equality از یک اشتباه رابطی قابل پیشگیری جلوگیری می‌کند.

آماده‌سازی یک‌بار، سپس اجرای پرس‌وجو

نمونهٔ زیر را در08-binary-search.mjs ذخیره و باNode.js اجرا کنید. prepareNumbers مرتب‌سازی نمی‌کند؛ ورودی نامرتب را رد می‌کند تا خطا پنهان نماند. هسته فقط روی نتیجهٔ همان مرحله مجاز است و ورودی مرتب را دوباره کامل نمی‌خواند. این تصمیم هم برای روشن‌بودن تحلیل هزینه و هم برای جلوگیری از بررسی تکراری است. قرار نیست تابعی با نام Prepared را آزادانه روی هر آرایهٔ ناشناخته فراخوانی کنیم؛ پیش‌شرط نوشته‌شده بخشی از قرارداد استفاده است.

import assert from 'node:assert/strict';
function prepareNumbers(input) {
  if (!Array.isArray(input) || input.length > 100_000) {
    throw new TypeError('Expected an array of at most 100000 numbers');
  }
  const copy = [];
  for (let i = 0; i < input.length; i += 1) {
    if (!Object.hasOwn(input, i) || !Number.isSafeInteger(input[i])) {
      throw new TypeError('Expected dense safe-integer data');
    }
    if (i > 0 && input[i] < input[i - 1]) throw new RangeError('Data must be sorted');
    copy.push(input[i]);
  }
  return Object.freeze(copy);
}
// Precondition: a is the immutable result of prepareNumbers.
function binaryIndexPrepared(a, key) {
  if (!Number.isSafeInteger(key)) throw new TypeError('Expected an integer key');
  let lo = 0, hi = a.length;
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (a[mid] < key) lo = mid + 1;
    else if (a[mid] > key) hi = mid;
    else return mid;
  }
  return -1;
}
const input = [4, 9, 15, 23, 31, 46];
const prepared = prepareNumbers(input);
assert.equal(binaryIndexPrepared(prepared, 31), 4);
assert.equal(binaryIndexPrepared(prepared, 22), -1);
assert.equal(binaryIndexPrepared(prepared, 4), 0);
assert.equal(binaryIndexPrepared(prepared, 46), 5);
assert.equal(binaryIndexPrepared(prepareNumbers([]), 4), -1);
assert.equal(binaryIndexPrepared(prepareNumbers([4]), 4), 0);
assert.equal(binaryIndexPrepared(prepareNumbers([4]), 3), -1);
assert.throws(() => prepareNumbers([4, 2]), RangeError);
assert.throws(() => prepareNumbers([4, NaN]), TypeError);
assert.throws(() => prepareNumbers([, 4]), TypeError);
assert.throws(() => binaryIndexPrepared(prepared, '31'), TypeError);
input[0] = 100;
assert.equal(prepared[0], 4);
console.log(`31: ${binaryIndexPrepared(prepared, 31)}, 22: ${binaryIndexPrepared(prepared, 22)}`);

خروجی31: 4, 22: -1 است. آزمون تغییر input نشان می‌دهد نسخهٔ آماده‌شده مستقل است. اما هزینهٔ ساخت این نسخه را نباید صفر حساب کنیم: بررسی و کپی، متناسب با تعداد عناصر کار و حافظه می‌خواهد. هستهٔ جست‌وجو روی نسخهٔ آماده، حافظهٔ کمکی ثابت و در بدترین حالت تعداد بررسیِ عنصر میانیِ لگاریتمی دارد؛ با حداکثر دو مقایسهٔ کلید در هر دور، شمار مقایسه‌ها هم از همین مرتبه است. اگر هر بار پیش از یک پرس‌وجو، تمام آرایه را اعتبارسنجی کنید، کل فراخوانی دیگر صرفاًO(log n) نیست. نام الگوریتم جای تحلیل مسیر کامل را نمی‌گیرد.

تکرارها؛ پیدا کردن یک رخداد با اولین رخداد فرق دارد

در[۴،۹،۹،۹،۱۵]، الگوریتم قبلی ممکن است شاخص۲ را برگرداند. این پاسخ طبق قرارداد «یک رخداد» درست است، اما برای خواستهٔ «اولین۹» کافی نیست. نسخهٔ بعد، محل نخستین مقدار بزرگ‌تر یا مساوی هدف را می‌یابد؛ این محل lower bound نامیده می‌شود. وقتی مقدار وسط با هدف برابر است، هنوز به چپ می‌رویم، چون ممکن است برابر دیگری زودتر وجود داشته باشد. پس از خالی‌شدن بازه، باید جداگانه بررسی کنیم محل به‌دست‌آمده واقعاً خود هدف را دارد.

firstIndexPrepared(a, key):
    lo ← 0 ; hi ← طول a
    تا زمانی که lo < hi:
        mid ← lo + کف((hi - lo) / 2)
        اگر a[mid] < key: lo ← mid + 1
        وگرنه: hi ← mid
    اگر lo < طول a و a[lo] = key: برگردان lo
    برگردان -1

برای۹ در همان آرایه، جفت مرزها از(۰،۵) باوسط۲ به(۰،۲) می‌رسد؛ وسط۱ نیز۹ است، پس(۰،۱) می‌شود؛ مقدار وسط۰ برابر۴ است، پس(۱،۱) و پایان. شاخص۱ نخستین رخداد است. برای۸ هم مرز نهایی۱ می‌شود، اما مقدار آن۹ است؛ بنابراین نتیجه−1 خواهد بود. «محل درج برای حفظ ترتیب» و«پیدا شدن هدف» دو خروجی متفاوت‌اند. همین بررسی پایانی، مرز قراردادی این دو مسئله را روشن می‌کند.

import assert from 'node:assert/strict';
// Precondition: a is a dense, ascending array of safe integers; do not modify it.
function firstIndexPrepared(a, key) {
  if (!Number.isSafeInteger(key)) throw new TypeError('Expected an integer key');
  let lo = 0, hi = a.length;
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (a[mid] < key) lo = mid + 1;
    else hi = mid;
  }
  return lo < a.length && a[lo] === key ? lo : -1;
}
const a = Object.freeze([4, 9, 9, 9, 15]);
assert.equal(firstIndexPrepared(a, 9), 1);
assert.equal(firstIndexPrepared(a, 4), 0);
assert.equal(firstIndexPrepared(a, 15), 4);
assert.equal(firstIndexPrepared(a, 8), -1);
assert.equal(firstIndexPrepared([], 9), -1);
assert.equal(firstIndexPrepared([9], 9), 0);
assert.equal(firstIndexPrepared([9, 9], 9), 0);
assert.equal(firstIndexPrepared([1, 3], 5), -1);
console.log(`first 9: ${firstIndexPrepared(a, 9)}, missing 8: ${firstIndexPrepared(a, 8)}`);

نمونهٔ مستقل08-first-index.mjs، first 9: 1, missing 8: -1 چاپ می‌کند. این بلوک، هستهٔ الگوریتم روی دادهٔ معتبر است؛ برای دادهٔ فایل یا شبکه باید مرحلهٔ آماده‌سازی نمونهٔ قبل را به کار ببرید. چند آزمایش کوچک را دستی هم انجام دهید: آرایهٔ خالی، تک‌عضوی، همهٔ مقدارها برابر و هدفی بزرگ‌تر از همه. در مورد آخر، lo ممکن است برابرطول شود؛ شرط lo < a.length از خواندن شاخصی بیرون محدوده جلوگیری می‌کند.

چه زمانی انتخاب خوبی است؟

برای یک فهرست نامرتب و فقط یک پرس‌وجو، یک جست‌وجوی خطی معمولاً طراحی ساده‌تری دارد؛ مرتب‌سازی اضافه باید توجیه شود. برای دادهٔ ثابت و پرس‌وجوهای زیاد، یک‌بار آماده‌سازی و بارها جست‌وجو ارزش بررسی دارد. اگر پس از هر تغییر، ترتیب از بین برود، هزینهٔ حفظ ترتیب را هم باید حساب کرد. همچنین شاخص خروجی مربوط به نسخهٔ مرتب است و الزاماً شاخص فهرست اولیه نیست. اگر مکان اولیه لازم است، شناسه یا شاخص اولیه را همراه ردیف نگه دارید.

در این درس، یک مقایسهٔ عددی و دسترسی به خانهٔ آرایه را در مدل آموزشی با هزینهٔ ثابت در نظر می‌گیریم. نصف‌کردن بازه توضیح می‌دهد چرا تعداد مراحل با افزایش ورودی، مانند پیمایش تک‌تک رشد نمی‌کند؛ اما زمان دقیق به محیط، داده و هزینهٔ آماده‌سازی وابسته است. برای بحث کامل‌تر هزینه و حافظه، به https://www.darsavand.com/resources/javascript-runtime-cost-complexity مراجعه کنید. این تحلیل ادعای سریع‌ترین‌بودن در همهٔ برنامه‌ها، موتورهای جاوااسکریپت یا اندازه‌های ورودی نیست.

نمونه‌سؤال‌های تألیفی و پاسخ تشریحی

سؤال۱: در [4,9,15,23,31,46] با بازهٔ نیمه‌باز، جست‌وجوی۲۲ را ردگیری کنید.

پاسخ۱: آغاز lo=0 وhi=6 است؛ mid=3 مقدار۲۳ دارد، پسhi=3. سپسmid=1 مقدار۹ دارد، پسlo=2. اکنونmid=2 مقدار۱۵ دارد، پسlo=3. چونlo=hi=3، بازه خالی است و خروجی−1 می‌شود. از خالی‌شدن بازه، نتیجهٔ نبود هدف را می‌گیریم؛ عدد۲۲ را با شاخص۲۲ یا طول آرایه اشتباه نمی‌کنیم.

سؤال۲: چرا hi=mid-1 در الگوریتم نیمه‌باز این درس غلط است؟ کوچک‌ترین مثال بسازید.

پاسخ۲: آرایه[1,3] وهدف۱ را بگیرید. ابتداlo=0 وhi=2، پسmid=1 و مقدار۳ است. اگرhi=mid-1 قرار دهیم،hi=0 می‌شود و عنصر شاخص۰ بدون بررسی حذف می‌شود. الگوریتم به‌غلط−1 می‌دهد. در قرارداد نیمه‌باز بایدhi=mid باشد. قاعدهٔ به‌ظاهر مشابه در الگوریتم بازهٔ بسته، نباید بدون تغییر بقیهٔ قرارداد کپی شود.

سؤال۳: برای فقط یک پرس‌وجو در فهرست نامرتب، آیا مرتب‌کردن و جست‌وجوی دودویی همیشه بهتر است؟

پاسخ۳: خیر. باید هزینهٔ مرتب‌سازی، کپی، بررسی داده و نگهداری ترتیب را هم حساب کرد. جست‌وجوی خطی یک عبور دارد و به مرتب‌سازی نیاز ندارد. اگر تعداد زیادی پرس‌وجو روی دادهٔ ثابت انجام شود، هزینهٔ آماده‌سازی ممکن است بین پرس‌وجوها سرشکن شود؛ تعداد پرس‌وجو، اندازهٔ داده و تغییرپذیری آن تصمیم را عوض می‌کنند. یک اجرای کوچک با زمان‌سنج، قاعدهٔ عمومی برای همهٔ ورودی‌ها نمی‌سازد.

معیار تحویل و منابع رسمی

در تحویل تمرین، نوع ترتیب، قرارداد بازه و معنای خروجی را بنویسید. باید یک جست‌وجوی موفق، یک جست‌وجوی ناموفق و یک مثال تکراری را بدون اجرای کامپیوتر ردگیری کنید. سپس همان ورودی‌ها را اجرا و تفاوت را بررسی کنید. اشتباه مرزها را با عوض‌کردن تصادفی <= و< حل نکنید؛ ابتدا مشخص کنید کدام مرز داخل بازه است. منابع زیر برای مطالعهٔ تکمیلی‌اند؛ متن، نمونه‌ها و آزمون‌های این درس تألیف مستقل تحریریه درس‌آوند هستند.

Harvard CS50x — Algorithms: https://cs50.harvard.edu/x/notes/3/
Princeton — BinarySearch API: https://algs4.cs.princeton.edu/code/javadoc/edu/princeton/cs/algs4/BinarySearch.html
MIT — Searching and Sorting: https://ocw.mit.edu/courses/6-0001-introduction-to-computer-science-and-programming-in-python-fall-2016/resources/lecture-12-searching-and-sorting/

فایل مثال‌ها، راهنمای فارسی اجرا و عیب‌یابی، پروژهٔ گزارش نمره‌ها و آزمون جمع‌بندی تألیفی با پاسخ تشریحی، رایگان در صفحهٔ بستهٔ تمرین همین دوره ارائه می‌شود:
https://www.darsavand.com/resources/computer-algorithms-practice-kit
تألیف و مثال‌های اختصاصی: تحریریه درس‌آوند.