ویکی‌پدیا

الگوریتم جستجوی دودویی: تفاوت میان نسخه‌ها

نمایش تاریخچه به صورت تعاملی
→ تفاوت قدیمی‌ترتفاوت جدیدتر ←
محتوای حذف‌شده محتوای افزوده‌شده
دیداریویکی‌متن
Rezabot (بحث | مشارکت‌ها)
ربات‌ها، مدیران رباتیک
۴٬۴۱۱٬۲۶۸ ویرایش‌ها
جز افزودن جعبه> (درخواست کاربر:Wikimostafa) +
ابرابزار
خط ۵:
|caption=Visualization of the binary search algorithm where 7 is the target value
|data=[[آرایه (ساختار داده)]]
|time=[[نماد O بزرگ| O(log n)]]
|space=[[نماد O بزرگ|O(1)]]
|best-time=[[نماد O بزرگ| O(log n)]]
|average-time=[[نماد O بزرگ|O(1)]]
|optimal=Yes
}}
'''الگوریتم جستجوی دودویی''' {{به انگلیسی|Binary Search}}، تکنیکی است برای یافتن یک مقدار عددی از میان مجموعه‌ای از اعداد مرتب. این متد محدودهٔ جستجو را در هر مرحله به نصف کاهش می‌دهد، بنابراین هدف مورد نظر یا به زودی پیدا می‌شود یا مشخص می‌شود که مقدار مورد جستجو در فهرست وجود ندارد.
 
جستجوی دودویی فقط در آرایه‌های مرتب استفاده می‌شود. در این روش عنصر مورد نظر با خانه وسط آرایه مقایسه می‌شود اگر با این خانه برابر بود جستجو تمام می‌شود اگر عنصر مورد جستجو از خانه وسط بزرگتر بود جستجو در بخش بالایی آرایه و در غیر این صورت جستجو در بخش پایینی آرایه انجام می‌شود (فرض کرده ایمکرده‌ایم آرایه به صورت صعودی مرتب شده استشده‌است) این رویه تا یافتن عنصر مورد نظر یا بررسی کل [[خانه هایخانه‌های]] آرایه ادامه می یابدمی‌یابد.
 
جستجوی دودویی نمونه‌ای از [[الگوریتم|الگوریتمهای]]های [[تقسیم و غلبه]] {{انگلیسی|Divide and conquer}} می‌باشد.
 
== مقدمه ==
پیدا کردن اندیس یک عنصر خاص در یک لیست مرتب شده مفید است زیرا با استفاده از اندیس داده شده می‌توان به سایر اطلاعات مربوطه دست یافت.
 
فرض کنید داده ساختاری شامل مجموعه‌ای از اطلاعات نام آدرس و شماره تلفن و غیره‌است و [[آرایه]] ای که نام‌ها را در بر دارددربردارد از ۱ تا N شماره‌گذاری شده‌است، یک در خواست می‌تواند این باشد: شماره فردی به نام X چند است. برای پاسخ دادن به این سؤال [[آرایه]] مورد نظر باید جستجو شده و اندیس مربوط به نام داده شده در صورت وجود برگردانده شود، در این حالت شماره تلفن ذخیره شده در آرایه تلفن‌ها در این اندیس، همان شماره فرد X است و به همین ترتیب برای آدرس و غیره نیز می‌توان عمل کرد.
== خواص درخت دودویی ==▼
 
▲== خواص درخت دودویی ==
n تعداد گره‌ها در یک [[درخت دودویی]] کامل است و با استفاده از این فرمول می‌توان آن را یافت ''<math>n = 2^{h+1}-1</math>'' (در آن h عمق درخت است)
N تعداد گره‌ها در یک درخت دودویی کامل است حداقل برابر ''<math>n = 2^{h}</math>'' و حداکثر برابر''<math>n = 2^{h+1}-1</math>'' ( h عمق درخت است)
L تعدادی از گره‌های برگ در درخت دودویی کامل است و با استفاده از فرمول ''<math>L = 2^h</math>'' محاسبه می گرددمی‌گردد.
 
N تعداد گره‌ها در یک درخت دودویی کامل نیز می‌تواند با استفاده فرمول ''<math>n = 2L-1</math>'' محاسبه می‌شود. (L، تعدادی از گره‌های برگ در درخت است.)
 
تعدادی از لینک‌های تهی (فرزندان غایب از گره هاگره‌ها) در یک درخت دودویی کامل از n گره<math>(n+1)</math>
تعداد ''<math>n-L</math>'' از گره‌های داخلی در یک درخت دودویی کامل از n گره (گره‌های غیر برگ) <math>\lfloor n/2 \rfloor</math>.
برای هر درخت غیر تهی با گره‌های برگ <math>n_0</math> و <math>n_2</math> گره‌ها از درجه 2 <math>n_0 = n_2 + 1</math>.
خط ۳۶:
 
N = تعداد کل گره
B = تعداد شاخه هاشاخه‌ها
:::''n''<sub>0</sub>, ''n''<sub>1</sub>, ''n''<sub>2</sub> برای نشان دادن تعداد گره بدون فرزند، تنها یک فرزند و دو فرزند بود
:::''B'' = ''n'' - 1 (از آنجا که تمام گره‌ها به جز گره ریشه از شاخه واحد)
خط ۵۰:
فرض کنید تعداد اعداد ممکن برابر N است، بنابراین <math>\lceil\log_2 N\rceil </math> سؤال لازم است تا عدد مورد نظر پیدا شود چون هر سؤال فضای جستجو را نصف می‌کند.
 
حتی اگر محدودهٔ اعداد مورد نظر نا محدود باشد (یعنی توسط N محدود نشده باشد) باز هم می‌توان با حداکثر <math>2\lceil \log_2 k \rceil </math> مرحله (که K عدد انتخاب شده‌است) عدد مورد نظر را یافت . بدین ترتیب که با شروع از یک و دو برابر کردن آن در هر مرحله ابتدا مرز بالایی را پیدا نموده و سپس عدد خواسته شده را پیدا می‌کنیم. به عنوان مثال اگر عدد انتخاب شده ۱۱ باشد ما می‌توانیم ترتیب پرسش‌های زیر را برای پیدا کردن عدد دنبال کنیم: ۱ ← ۲ ← ۴ ← ۸ ← ۱۶ ← ۱۲ ← ۱۰ ← ۱۱.
 
هم چنین می‌توان این تکنیک را گسترش داد تا شامل [[اعداد منفی]] نیز بشود، به عنوان مثال حدس‌های زیر دنبال می‌شوند تا عدد ۱۳- پیدا شود: ۰ ← ۱- ← ۲- ← ۴- ← ۸- ← ۱۶- ← ۱۲- ← ۱۴- ← ۱۳-.
 
=== لیست‌های کلمات ===
انسان‌ها معمولاً ترکیبی از جستجوی دودویی و [[الگوریتم]]‌های جستجوی الحاقی را هنگام جستجوی دفترچه تلفن به کار می‌برند. بعد از حدس اولیه ما از این حقیقت استفاده می کنیممی‌کنیم که ورودی‌ها مرتب اند و در نتیجه سریع تر به هدف می رسیممی‌رسیم. مثلاً وقتی به دنبال "«کریمی"» می گردیممی‌گردیم اگر "«گنجی"» و "«قلی پور"» پیدا شوند ما می‌توانیم به صفحه‌ای بین حدس‌های قبلی مراجعه کنیم و اگر مثلاً "«کمالی"» را نشان می‌داد می دانیممی‌دانیم که صفحهٔ مورد نظر جایی بین "«قلی پور"» و "«کمالی"» خواهد بود.
 
== تابع ==
[[پرونده:BinarySearchStats63.png|بندانگشتی|چپ|400px|تکرار برای ''N'' <64]]
برای این که وارد جزئیات تابع شویم باید قراردادهای رسمی تری را تعریف کنیم. ایده اولیه این است که داده ساختاری وجود دارد که به صورت آرایه A نمایش داده می‌شود، و المان‌های آن به صورت A(1), A(2),…,A توصیف می‌شوند و به هر ترتیبی قابل دستیابی‌اند.
 
داده ساختاری شامل دادهٔ دیگری به نام Key می‌شود، آرایه به گونه‌ای مرتب می‌شود که A(1).Key <= A(2).Key و ... ….
 
هدف این است که مقدار x داده شده و اندیس p پیدا شود به‌طوری‌که A(p).Key = x.
خط ۶۹:
== پیاده‌سازی ==
=== تکرار ===
Niklaus Wirth این الگوریتم را در پاسکال ارائه کرده‌است:
{{چپ‌چین}}
i := 1;
j := N; {array size: var A : array [1..N] of integer}
repeat
k := (i + j) div 2;
if x> A[k] then
i := k + 1
else
j := k - 1;
until (A[k] = x) or (i> j);
{{پایان چپ‌چین}}
خط ۸۵:
پیاده‌سازی متداول این تابع توسط [[الگوریتم بازگشتی]] زیر می‌باشد:
{{چپ‌چین}}
BinarySearch(A[0..N-1], value, low, high) {
if (high <low)
return -1 // not found
mid = low + ((high - low) / 2) // Note: not (low + high) / 2 !!
if (A[mid]> value)
return BinarySearch(A, value, low, mid-1)
else if (A[mid] <value)
return BinarySearch(A, value, mid+1, high)
else
return mid // found
}
{{پایان چپ‌چین}}
 
خط ۱۰۱:
 
{{چپ‌چین}}
static bool BinarySearch(int[] A, int x, int i, int j) {
if (i> j)
return false;
int m = (i + j) / 2;
if (x> A[m])
return BinarySearch(A, x, m + 1, j);
else if (x <A[m])
return BinarySearch(A, x, i, m - 1);
else
return true;
}
{{پایان چپ‌چین}}
 
خط ۱۱۷:
{{پانویس}}
{{چپ‌چین}}
* [[دانلد کنوت]]. ''The Art of Computer Programming'', Volume 3: ''Sorting and Searching'', Third Edition. Addison-Wesley, 1997. {{ISBN|0-201-89685-0|en}}. Section 6.2.1: Searching an Ordered Table, pp.&nbsp; 409–426.
* Kruse, Robert L. : "Data Structures and Program Design in C++", Prentice-Hall, 1999, {{ISBN|0-13-768995-0|en}}, page 280.
* http://en.wikipedia.org/wiki/Binary_search_algorithm
{{پایان چپ‌چین}}
 
== پیوند به بیرون ==
{{چپ‌چین}}
* [http://www.nist.gov/dads/HTML/binarySearch.html NIST Dictionary of Algorithms and Data Structures: binary search]
* [http://www.paked.net/subject_pages/computer_science/prog1.htm Binary Search using C++ ]
* [http://a4.users.phpclasses.org/browse/package/4799.html Binary Search using PHP ]
* [http://msdn.microsoft.com/en-us/library/w4e7fxsh(v=vs.110).aspx Binary Search using CSharp]
*[ ]
برگرفته از «https://fa.wikipedia.org/wiki/الگوریتم_جستجوی_دودویی»