سلام,
در کتاب مدرسان شریف در پاسخ یکی از سوالات چنین نوشته شده بود:
برای جستجوی ناموفق عدد -۱ در آرایه پایین، دو مقایسه لازم است.
[۱,۳,۵,۹,۱۱]
اما سوالم اینه که بر چه اساسی ۲ مقایسه انجام میشه، البته براحتی می تونم مقایسه ۵ یا ۴ را محاسبه کنم اما -۱ رو نمی دونم چرا ۲ بار شده!؟
لطفا اگر اطلاعات کافی نبودند، هر چه لازم دارید بفرمایید تا تکمیلش کنم.
سلام.
سوال ساده ای هست. روند جستجوی دودویی رو بر روی اعداد داده شده اعمال کنید.
می دونیم که -۱ در میان عناصر نیست، پس سوال رو میشه به این صورت پرسید:"بعد از چند بار مقایسه متوجه میشویم که -۱ در میان عناصر وجود ندارد". ابتدا بر اساس جستجوی دودویی -۱ با ۵ مقایسه میشه (بر اساس ۲/ (mid = (low+high) و چون -۱ از ۵ کوچکتر هست به قسمت پایینی عناصر (یعنی ۳ ۱ ) مراجعه میکنه. باز روند جستجو رو از سر میگیریم. طبق همین فرمول بالا -۱ با mid که ۱ باشه مقایسه میشه.
پس در کل برای عدم موفقیت جستجوی -۱ در عناصر صورت سوال، ۲ مقایسه (با اعداد ۵ و ۱) انجام میشه.
(۱۷ شهریور ۱۳۹۲ ۰۳:۵۱ ب.ظ)azad_ahmadi نوشته شده توسط: سلام.
سوال ساده ای هست. روند جستجوی دودویی رو بر روی اعداد داده شده اعمال کنید.
می دونیم که -۱ در میان عناصر نیست، پس سوال رو میشه به این صورت پرسید:"بعد از چند بار مقایسه متوجه میشویم که -۱ در میان عناصر وجود ندارد". ابتدا بر اساس جستجوی دودویی -۱ با ۵ مقایسه میشه (بر اساس ۲/ (mid = (low+high) و چون -۱ از ۵ کوچکتر هست به قسمت پایینی عناصر (یعنی ۳ ۱ ) مراجعه میکنه. باز روند جستجو رو از سر میگیریم. طبق همین فرمول بالا -۱ با mid که ۱ باشه مقایسه میشه.
پس در کل برای عدم موفقیت جستجوی -۱ در عناصر صورت سوال، ۲ مقایسه (با اعداد ۵ و ۱) انجام میشه.
خیلی ممنونم، از قدیم گفته اند مسئله که حل شود آسان شود، واقعا حق با شماست! متشکرم.