الگوریتم جستجوی دودویی: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
جز ویرایش 5.73.227.110 (بحث) به آخرین تغییری که مهراد قطب الدینی انجام داده بود واگردانده... |
جز سوال به سؤال، replaced: سوال ← سؤال (3) با استفاده از AWB |
||
خط ۹:
پیدا کردن اندیس یک عنصر خاص در یک لیست مرتب شده مفید است زیرا با استفاده از اندیس داده شده می‌توان به سایر اطلاعات مربوطه دست یافت.
فرض کنید داده ساختاری شامل مجموعه‌ای از اطلاعات نام٫ آدرس و شماره تلفن و غیره‌است و [[آرایه]] ای که نام‌ها را در بر دارد از ۱ تا N شماره گذاری شده‌است، یک در خواست می‌تواند این باشد: شماره فردی به نام X چند است. برای پاسخ دادن به این
== خواص درخت دودویی ==
خط ۳۷:
این بازی‌های ساده با چیزی شبیه این شروع می‌شوند:" من عددی را بین ۴۰ و ۶۰ در نظر گرفته‌ام و تو آن را حدس می‌زنی و من با این پاسخ‌ها تو را راهنمایی می‌کنم: کمتر، بیشتر و بله!
فرض کنید تعداد اعداد ممکن برابر N است، بنابراین <math>\lceil\log_2 N\rceil </math>
حتی اگر محدودهٔ اعداد مورد نظر نا محدود باشد(یعنی توسط N محدود نشده باشد) باز هم می‌توان با حداکثر <math>2\lceil \log_2 k \rceil </math> مرحله(که K عدد انتخاب شده‌است) عدد مورد نظر را یافت .بدین ترتیب که با شروع از یک و دو برابر کردن آن در هر مرحله ابتدا مرز بالایی را پیدا نموده و سپس عدد خواسته شده را پیدا می‌کنیم. به عنوان مثال اگر عدد انتخاب شده ۱۱ باشد ما می‌توانیم ترتیب پرسش‌های زیر را برای پیدا کردن عدد دنبال کنیم: ۱ ← ۲ ← ۴ ← ۸ ← ۱۶ ← ۱۲ ← ۱۰ ← ۱۱.
خط ۸۹:
{{پانویس}}
{{چپ‌چین}}
* [[دانلد کنوت]]. ''The Art of Computer Programming'', Volume 3: ''Sorting and Searching'', Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Section 6.2.1: Searching an Ordered Table, pp. 409–426.
* Kruse, Robert L.: "Data Structures and Program Design in C++", Prentice-Hall, 1999, ISBN 0-13-768995-0, page 280.
* http://en.wikipedia.org/wiki/Binary_search_algorithm
| |||