الگوریتم جستجوی دودویی ( به انگلیسی: Binary Search ) یا جستجوی دودویی خوارزمی، تکنیکی است برای یافتن یک مقدار عددی از میان مجموعه ای از اعداد مرتب. این متد محدودهٔ جستجو را در هر مرحله به نصف کاهش می دهد، بنابراین هدف مورد نظر یا به زودی پیدا می شود یا مشخص می شود که مقدار مورد جستجو در فهرست وجود ندارد.
جستجوی دودویی فقط در آرایه های مرتب استفاده می شود. در این روش عنصر مورد نظر با خانه وسط آرایه مقایسه می شود اگر با این خانه برابر بود جستجو تمام می شود اگر عنصر مورد جستجو از خانه وسط بزرگتر بود جستجو در بخش بالایی آرایه و در غیر این صورت جستجو در بخش پایینی آرایه انجام می شود ( فرض کرده ایم آرایه به صورت صعودی مرتب شده است ) این رویه تا یافتن عنصر مورد نظر یا بررسی کل خانه های آرایه ادامه می یابد.
جستجوی دودویی نمونه ای از الگوریتمهای تقسیم و غلبه ( به انگلیسی: Divide and conquer ) می باشد.
پیدا کردن اندیس یک عنصر خاص در یک لیست مرتب شده مفید است زیرا با استفاده از اندیس داده شده می توان به سایر اطلاعات مربوط دست یافت.
فرض کنید داده ساختاری شامل مجموعه ای از اطلاعات نام آدرس و شماره تلفن و غیره است و آرایه ای که نام ها را دربردارد از ۱ تا N شماره گذاری شده است، یک در خواست می تواند این باشد: شماره فردی به نام X چند است. برای پاسخ دادن به این سؤال آرایه مورد نظر باید جستجو شده و اندیس مربوط به نام داده شده در صورت وجود برگردانده شود، در این حالت شماره تلفن ذخیره شده در آرایه تلفن ها در این اندیس، همان شماره فرد X است و به همین ترتیب برای آدرس و غیره نیز می توان عمل کرد.
n تعداد گره ها در یک درخت دودویی کامل است و با استفاده از این فرمول می توان آن را یافت n = 2 h + 1 − 1 ( در آن h عمق درخت است ) N تعداد گره ها در یک درخت دودویی کامل است حداقل برابر n = 2 h و حداکثر برابر n = 2 h + 1 − 1 ( h عمق درخت است ) L تعدادی از گره های برگ در درخت دودویی کامل است و با استفاده از فرمول L = 2 h محاسبه می گردد.
N تعداد گره ها در یک درخت دودویی کامل نیز می تواند با استفاده فرمول n = 2 L − 1 محاسبه می شود. ( L، تعدادی از گره های برگ در درخت است )
تعدادی از لینک های تهی ( فرزندان غایب از گره ها ) در یک درخت دودویی کامل از n گره ( n + 1 ) تعداد n − L از گره های داخلی در یک درخت دودویی کامل از n گره ( گره های غیر برگ ) ⌊ n / 2 ⌋ . برای هر درخت غیر تهی با گره های برگ n 0 و n 2 گره ها از درجه 2 n 0 = n 2 + 1 .
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفجستجوی دودویی فقط در آرایه های مرتب استفاده می شود. در این روش عنصر مورد نظر با خانه وسط آرایه مقایسه می شود اگر با این خانه برابر بود جستجو تمام می شود اگر عنصر مورد جستجو از خانه وسط بزرگتر بود جستجو در بخش بالایی آرایه و در غیر این صورت جستجو در بخش پایینی آرایه انجام می شود ( فرض کرده ایم آرایه به صورت صعودی مرتب شده است ) این رویه تا یافتن عنصر مورد نظر یا بررسی کل خانه های آرایه ادامه می یابد.
جستجوی دودویی نمونه ای از الگوریتمهای تقسیم و غلبه ( به انگلیسی: Divide and conquer ) می باشد.
پیدا کردن اندیس یک عنصر خاص در یک لیست مرتب شده مفید است زیرا با استفاده از اندیس داده شده می توان به سایر اطلاعات مربوط دست یافت.
فرض کنید داده ساختاری شامل مجموعه ای از اطلاعات نام آدرس و شماره تلفن و غیره است و آرایه ای که نام ها را دربردارد از ۱ تا N شماره گذاری شده است، یک در خواست می تواند این باشد: شماره فردی به نام X چند است. برای پاسخ دادن به این سؤال آرایه مورد نظر باید جستجو شده و اندیس مربوط به نام داده شده در صورت وجود برگردانده شود، در این حالت شماره تلفن ذخیره شده در آرایه تلفن ها در این اندیس، همان شماره فرد X است و به همین ترتیب برای آدرس و غیره نیز می توان عمل کرد.
n تعداد گره ها در یک درخت دودویی کامل است و با استفاده از این فرمول می توان آن را یافت n = 2 h + 1 − 1 ( در آن h عمق درخت است ) N تعداد گره ها در یک درخت دودویی کامل است حداقل برابر n = 2 h و حداکثر برابر n = 2 h + 1 − 1 ( h عمق درخت است ) L تعدادی از گره های برگ در درخت دودویی کامل است و با استفاده از فرمول L = 2 h محاسبه می گردد.
N تعداد گره ها در یک درخت دودویی کامل نیز می تواند با استفاده فرمول n = 2 L − 1 محاسبه می شود. ( L، تعدادی از گره های برگ در درخت است )
تعدادی از لینک های تهی ( فرزندان غایب از گره ها ) در یک درخت دودویی کامل از n گره ( n + 1 ) تعداد n − L از گره های داخلی در یک درخت دودویی کامل از n گره ( گره های غیر برگ ) ⌊ n / 2 ⌋ . برای هر درخت غیر تهی با گره های برگ n 0 و n 2 گره ها از درجه 2 n 0 = n 2 + 1 .
wiki: الگوریتم جستجوی دودویی