جستجوی درون‌یابی
الگوریتم > تحلیل

اگر توزیع کلیدها تقریباً یکنواخت باشد، جستجوی درون یابی سریعتر از جستجوی دودویی، کلید x را پیدا می‌کند. برای نمونه، در مثال قبل، اگر x=۲۵ کوچکتر از [S[۳ می‌بود، جستجوی درون یابی، اندازه نمونه را از ۱۰ به ۲ کاهش می‌داد، حال آنکه جستجوی دودویی آن را فقط به ۴ کاهش می‌داد.
فرض کنید کلیدها به‌طور یکنواخت بین [S[۱ و [S[n توزیع شده باشند. منظور ما این است که احتمال پیدا شدن یک کلید انتخاب شده به‌طور تصادفی در یک محدوده خاص، مساوی احتمال پیدا شدن آن در هر محدوده دیگری با همان طول است. اگر چنین باشد، انتظار داریم x را تقریباً در محلی که جستجوی برون یابی تعیین کرده‌است، بیابیم و بنابراین، انتظار داریم کارایی جستجوی درون یابی در حالت میانگین بهتر از جستجوی دودویی باشد. در واقع، تحت شرایطی که کلیدها به‌طور یکنواخت توزیع شده‌اند، می‌توان نشان داد که پیچیدگی زمانی جستجوی درون یابی در حالت میانگین عبارت است از:
اگر n برابر با یک میلیارد باشد، (lg(lg n حدود ۵ است، حال آنکه lg n حدود ۳۰ است.
یک عیب جستجوی درون یابی، کارایی آن در بدترین حالت است. فرض کنید ۱۰ کلید داریم و مقادیر آن‌ها عبارتند از ۱، ۲، ۳، ۴، ۵، ۶، ۷، ۸، ۹ و ۱۰۰. اگر x برابر ۱۰ باشد، mid به کرات برابر low قرار داده می‌شود و x با هر یک از کلیدها مقایسه می‌شود. در بدترین حالت، جستجوی درون یابی تا حد جستجوی ترتیبی تنزل می‌یابد. توجه کنید که بدترین حالت، زمانی رخ می‌دهد که mid به کرات برابر low قرار داده می‌شود. شکل دیگری از جستجوی درون یابی که جستجوی درون یابی توانمند نامید می‌شود، این مشکل را با تعریف متغیر gap حل می‌کند، بطوریکه mid-low و high-mid همواره بزرگتر از gap هستند. به gap مقدار اولیه زیر را می‌دهیم:
و mid را با استفاده از فرمول قبلی برای درون یابی خطی محاسبه می‌کنیم. پس از آن محاسبه، مقدار mid احتمالاً با محاسبه زیر تغییر می‌یابد:
در مثالی که x=۲۰ و کلیدها برابر ۱، ۲، ۳، ۴، ۵، ۶، ۷، ۸، ۹ و ۱۰۰ بودند، به gap مقدار اولیه
 \lfloor (10-1+1)^{\frac {1}{2}}\rfloor =3، به mid مقدار اولیه ۱ داده می‌شود و داریم:
به این ترتیب تضمین می‌شود که اندیس به کار رفته برای مقایسه، حداقل به اندازه gap از low و high دور است. هر گاه جستجو به دنبال x در زیر آرایه حاوی تعداد بزرگتری از عناصر آرایه ادامه یابد، مقدار gap دو برابر می‌شود، ولی هرگز بزرگتر از نصف تعداد عناصر موجود در آن زیر آرایه نمی‌شود. برای نمونه، در مثال قبل، جستجو به دنبال x، در زیر آرایه بزرگتر از [S[۵ تا [S[۱۰ ادامه می‌یابد. بنابراین gap را دو برابر می‌کنیم. با این تفاوت که در این مورد، زیر آرایه حاوی تنها شش عنصر است و با دو برابر کردن gap مقدار آن از تعداد عناصر موجود در زیر آرایه تجاوز می‌کند. gap را دو برابر می‌کنیم تا به سرعت از زیرآرایه‌های بزرگ گریز کنیم. هنگامی که معلوم می‌شود x در زیر آرایه حاوی تعداد کوچکتری از عناصر است، به gap همان مقدار اولیه اش را می‌دهیم.
با این فرضیات که کلیدها به‌طور یکنواخت توزیع شده‌اند و احتمال وجود x در همه محلهای آرایه یکسان است، پیچیدگی زمانی در حالت میانگین برای جستجوی درون یابی توانمند برابر  ((\Theta (lg(lgn است. پیچیدگی زمانی آن در بدترین حالت به  (\Theta ((lgn)^{2} تعلق دارد، که از جستجوی دودویی بدتر ولی از جستجوی درون یابی بسیار بهتر است.
چند محاسبه اضافی در جستجوی درون یابی توانمند، نسبت به جستجوی درون یابی و در جستجوی درون یابی نسبت به جستجوی دودویی وجود دارد. در عمل باید تحلیل شود که آیا صرفه جویی در محاسبات ارزش این افزایش در محاسبات را دارد یا خیر.
جستجوهای شرح داده شده در اینجا، در مورد کلمات نیز کاربرد دارد زیرا کلمات را می‌توان به راحتی به اعداد کدگذاری کرد. بنابراین، می‌توانیم روش جستجوی دودویی اصلاح شده را در جستجوی کتاب راهنمای تلفن به کار گیریم.