موضوع مقاله: جستجوی درون‌یابی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # جستجوی درون‌یابی | مقدمه: به‌طور کلی در علوم کامپیوتر و ریاضیات، یک الگوریتم جستجو، الگوریتمی است که یک مسئله را به عنوان ورودی می‌گیرد و بعد از ارزیابی کردن راه حل‌های ممکن، یک راه حل برای آن مسئله برمی گرداند.مجموعهٔ راه حل‌های ممکن برای یک مسئله را فضای جستجو می‌نامند. | ## بخش 1: جستجوی درون‌یابی | برای یافتن شماره تلفن «کالین، کالی» در دفترچه تلفن، چیزی بیش از مقایسه کلیدها را انجام می‌دهیم. یعنی ما از میانه کتاب شروع نمی‌کنیم زیرا می‌دانیم که «ک»ها در کجای دفترچه قرار دارند. فرض کنید کلید x را در میان ۱۰ عدد صحیح جستجو می‌کنیم و می‌دانیم که عدد صحیح اول بین ۰ تا ۹، دومی بین ۱۰ تا ۱۹، سومی بین ۲۰ تا ۲۹، ... در این صورت اگر کلید x کوچکتر از صفر یا بزرگتر از ۹۹ باشد، می‌توان بی درنگ شکست را گزارش کرد و در غیر این صورت، فقط کافی است x را با مقایسه کنیم. ولی در برخی کاربردها منطقی است که فرض کنیم کلیدها از توزیع تقریباً یکنواختی برخوردارند. در چنین مواردی، بجای چک کردن آن که آیا x با کلید میانی برابر است، می‌توانیم چک کنیم که آیا x در موقعیتی که انتظار داریم آن را بیابیم، هست یا خیر. برای مثال، اگر فرض کنیم که ۱۰ کلید از توزیع یکنواختی برخوردارند، می‌توانیم انتظار داشته باشیم که x=۲۵ در موقعیت سوم قرار دارد و به جای مقایسه x با [S[۵ آن را با [S[۳ مقایسه می‌کنیم. سپس از درون یابی خطی برای تعیین تقریبی محل واقع شدن x استفاده می‌کنیم، یعنی محاسبه زیر را انجام می‌دهیم: برای مثال، اگر S[۱]=۴ و S[10]=۹۷ باشد و ما به دنبال x=۲۵ باشیم، محاسبه زیر را انجام می‌دهیم: الگوریتم الگوریتم جستجوی درون یابی، که در زیر می‌آید، به جای شیوه متفاوت محاسبه mid و کارهای اضافی، همانند جستجوی دودویی عمل می‌کند. برای نمونه، در مثال قبل، اگر x=۲۵ کوچکتر از [S[۳ می‌بود، جستجوی درون یابی، اندازه نمونه را از ۱۰ به ۲ کاهش می‌داد، حال آنکه جستجوی دودویی آن را فقط به ۴ کاهش می‌داد. | ## بخش 2: جستجوی درون‌یابی | منظور ما این است که احتمال پیدا شدن یک کلید انتخاب شده به‌طور تصادفی در یک محدوده خاص، مساوی احتمال پیدا شدن آن در هر محدوده دیگری با همان طول است. اگر چنین باشد، انتظار داریم x را تقریباً در محلی که جستجوی برون یابی تعیین کرده‌است، بیابیم و بنابراین، انتظار داریم کارایی جستجوی درون یابی در حالت میانگین بهتر از جستجوی دودویی باشد. در واقع، تحت شرایطی که کلیدها به‌طور یکنواخت توزیع شده‌اند، می‌توان نشان داد که پیچیدگی زمانی جستجوی درون یابی در حالت میانگین عبارت است از: اگر n برابر با یک میلیارد باشد، (lg(lg n حدود ۵ است، حال آنکه lg n حدود ۳۰ است. فرض کنید ۱۰ کلید داریم و مقادیر آن‌ها عبارتند از ۱، ۲، ۳، ۴، ۵، ۶، ۷، ۸، ۹ و ۱۰۰. توجه کنید که بدترین حالت، زمانی رخ می‌دهد که mid به کرات برابر low قرار داده می‌شود. به gap مقدار اولیه زیر را می‌دهیم: و mid را با استفاده از فرمول قبلی برای درون یابی خطی محاسبه می‌کنیم. پس از آن محاسبه، مقدار mid احتمالاً با محاسبه زیر تغییر می‌یابد: در مثالی که x=۲۰ و کلیدها برابر ۱، ۲، ۳، ۴، ۵، ۶، ۷، ۸، ۹ و ۱۰۰ بودند، به gap مقدار اولیه ، به mid مقدار اولیه ۱ داده می‌شود و داریم: به این ترتیب تضمین می‌شود که اندیس به کار رفته برای مقایسه، حداقل به اندازه gap از low و high دور است. هر گاه جستجو به دنبال x در زیر آرایه حاوی تعداد بزرگتری از عناصر آرایه ادامه یابد، مقدار gap دو برابر می‌شود، ولی هرگز بزرگتر از نصف تعداد عناصر موجود در آن زیر آرایه نمی‌شود. برای نمونه، در مثال قبل، جستجو به دنبال x، در زیر آرایه بزرگتر از [S[۵ تا [S[۱۰ ادامه می‌یابد. | ## بخش 3: جستجوی درون‌یابی | با این تفاوت که در این مورد، زیر آرایه حاوی تنها شش عنصر است و با دو برابر کردن gap مقدار آن از تعداد عناصر موجود در زیر آرایه تجاوز می‌کند. هنگامی که معلوم می‌شود x در زیر آرایه حاوی تعداد کوچکتری از عناصر است، به gap همان مقدار اولیه اش را می‌دهیم. با این فرضیات که کلیدها به‌طور یکنواخت توزیع شده‌اند و احتمال وجود x در همه محلهای آرایه یکسان است، پیچیدگی زمانی در حالت میانگین برای جستجوی درون یابی توانمند برابر است. پیچیدگی زمانی آن در بدترین حالت به تعلق دارد، که از جستجوی دودویی بدتر ولی از جستجوی درون یابی بسیار بهتر است. چند محاسبه اضافی در جستجوی درون یابی توانمند، نسبت به جستجوی درون یابی و در جستجوی درون یابی نسبت به جستجوی دودویی وجود دارد. در عمل باید تحلیل شود که آیا صرفه جویی در محاسبات ارزش این افزایش در محاسبات را دارد یا خیر. جستجوهای شرح داده شده در اینجا، در مورد کلمات نیز کاربرد دارد زیرا کلمات را می‌توان به راحتی به اعداد کدگذاری کرد. | ## جمع‌بندی | بنابراین، می‌توانیم روش جستجوی دودویی اصلاح شده را در جستجوی کتاب راهنمای تلفن به کار گیریم.