جستجوی باینری در مقابل جستجوی خطی
جستجوی خطی، که به عنوان جستجوی متوالی نیز شناخته می شود، ساده ترین الگوریتم جستجو است. با بررسی هر عنصر در لیست، مقدار مشخصی را در لیست جستجو می کند. جستجوی باینری همچنین روشی است که برای تعیین مکان یک مقدار مشخص در یک لیست مرتب شده استفاده می شود. روش جستجوی دودویی تعداد عناصر بررسی شده (در هر تکرار) را به نصف کاهش می دهد، و زمان صرف شده برای یافتن آیتم داده شده در لیست را کاهش می دهد.
جستجوی خطی چیست؟
جستجوی خطی ساده ترین روش جستجو است که هر عنصر را در لیست به صورت متوالی بررسی می کند تا زمانی که یک عنصر مشخص را پیدا کند.ورودی روش جستجوی خطی یک دنباله (مانند یک آرایه، مجموعه یا یک رشته) و موردی است که باید جستجو شود. خروجی اگر مورد مشخص شده در توالی ارائه شده باشد درست است یا اگر در دنباله نباشد نادرست است. از آنجایی که این روش تمام آیتم های لیست را تا زمانی که مورد مشخص شده پیدا شود بررسی می کند، در بدترین حالت قبل از یافتن عنصر مورد نیاز، تمام عناصر لیست را بررسی می کند. پیچیدگی جستجوی خطی o(n) است. بنابراین در نظر گرفته می شود که برای استفاده در هنگام جستجوی عناصر در لیست های بزرگ بسیار کند است. اما این بسیار ساده و آسان‌تر برای پیاده‌سازی است.
جستجوی باینری چیست؟
جستجوی باینری همچنین روشی است که برای مکان یابی یک آیتم مشخص شده در یک لیست مرتب شده استفاده می شود. این روش با مقایسه عنصر جستجو شده با عناصر وسط لیست شروع می شود. اگر مقایسه مشخص کند که دو عنصر برابر هستند، روش متوقف می شود و موقعیت عنصر را برمی گرداند. اگر عنصر جستجو شده بزرگتر از عنصر میانی باشد، روش را دوباره با استفاده از نیمه پایین لیست مرتب شده شروع می کند.اگر عنصر جستجو شده کمتر از عنصر میانی باشد، روش را تنها با استفاده از نیمه بالای لیست مرتب شده دوباره شروع می کند. اگر عنصر جستجو شده در لیست نباشد، روش یک مقدار منحصر به فرد را نشان می دهد که نشان می دهد. بنابراین، روش جستجوی دودویی، بسته به نتیجه مقایسه، تعداد عناصر مقایسه شده (در هر تکرار) را نصف می کند. در نتیجه، جستجوی باینری در زمان لگاریتمی اجرا می‌شود که منجر به عملکرد متوسط موردی o(log n) می‌شود.
تفاوت بین جستجوی باینری و جستجوی خطی چیست؟
اگرچه جستجوی خطی و جستجوی باینری هر دو روش های جستجو هستند، اما چندین تفاوت با هم دارند. در حالی که جستجوی دودویی در لیست های مرتب شده عمل می کند، جستجوی خطی می تواند روی لیست های مرتب نشده نیز عمل کند. مرتب‌سازی یک لیست معمولاً دارای پیچیدگی متوسط n log n است. اجرای جستجوی خطی نسبت به جستجوی باینری ساده و ساده است. اما، جستجوی خطی به دلیل عملکرد متوسط موردی o(n) برای استفاده در لیست های بزرگ بسیار کند است.از سوی دیگر، جستجوی باینری روش کارآمدتری در نظر گرفته می‌شود که می‌توان با فهرست‌های بزرگ از آن استفاده کرد. اما اجرای جستجوی دودویی می تواند بسیار مشکل باشد و یک مطالعه نشان داده است که کد دقیق برای جستجوی باینری را می توان تنها در پنج کتاب از بیست کتاب پیدا کرد.
