الگوریتم جستجوی دودویی
From Wikipedia, the free encyclopedia
الگوریتم جستجوی دودویی (به انگلیسی: Binary Search) یا جستجوی دودویی خوارزمی، تکنیکی است برای یافتن یک مقدار عددی از میان مجموعهای از اعداد مرتب. این متد محدودهٔ جستجو را در هر مرحله به نصف کاهش میدهد، بنابراین هدف مورد نظر یا به زودی پیدا میشود یا مشخص میشود که مقدار مورد جستجو در فهرست وجود ندارد.
این مقاله به دلیل یک مقدار نامرتب نیازمند تمیزکاری است. لطفاً تا جای امکان آنرا از نظر املا، انشا، چیدمان و درستی بهتر کنید، سپس این برچسب را بردارید. محتویات این مقاله ممکن است غیر قابل اعتماد و نادرست یا جانبدارانه باشد یا قوانین حقوق پدیدآورندگان را نقض کرده باشد. |
رده | الگوریتم جستجو |
---|---|
ساختمان داده | آرایه (ساختار داده) |
کارایی بدترین حالت | O(log n) |
کارایی بهترین حالت | O(1) |
کارایی متوسط | O(log n) |
پیچیدگی فضایی | O(1) |
جستجوی دودویی فقط در آرایههای مرتب استفاده میشود. در این روش عنصر مورد نظر با خانه وسط آرایه مقایسه میشود اگر با این خانه برابر بود جستجو تمام میشود اگر عنصر مورد جستجو از خانه وسط بزرگتر بود جستجو در بخش بالایی آرایه و در غیر این صورت جستجو در بخش پایینی آرایه انجام میشود (فرض کردهایم آرایه به صورت صعودی مرتب شدهاست) این رویه تا یافتن عنصر مورد نظر یا بررسی کل خانههای آرایه ادامه مییابد.
جستجوی دودویی نمونهای از الگوریتمهای تقسیم و غلبه (به انگلیسی: Divide and conquer) میباشد.