کارآیی الگوریتمی: تفاوت میان نسخه‌ها

low = mid + 1;

}

و در الگوریتم جستجوی دودویی در حالتی که x در آرایه موجود نباشد، در هر حلقهٔ while دو بار عدد x با <math>S[mid]</math> مقایسه می‌شود. اما در واقع اگر اجرایی کارا از الگوریتم توسط اسمبلر صورت گیرد در هر بار اجرای حلقهٔ while تنها یک بار x با <math>S[mid]</math> مقایسه می‌شود. در نتیجهٔ این مقایسه حالت مناسب بر اساس مقدار کد شرط تعیین می‌شود. با فرض اینکه الگوریتم جستجوی دودویی از این روش استفاده می‌کند، برای جستجوی عدد x در همان آرایهٔ ۱۶ عنصری که x از همهٔ عناصر آرایه بزرگتر است، این الگوریتم فقط ۵ مقایسه انجام می‌دهد که <math>log16+1=5</math> است (منظور، لگاریتم در مبنای 2 می‌باشد). و البته این بیشترین تعداد مقایسه هاست که با این روش صورت می‌گیرد. (در صورتی که x در آرایه موجود باشد تعداد مقایسه‌ها بیشتر نخواهد بود).

حال اگر تعداد عناصر آرایه دو برابر شود یعنی 32 عنصر داشته باشیم، تعداد مقایسات در الگوریتم جستجوی دودویی فقط ۱ مرتبه از حالت قبل بیشتر خواهد بود، یعنی زمانی که اولین مقایسه صورت می‌گیرد و آرایه به دو زیر آرایه تقسیم می‌شود. لذا باز هم در بدترین حالت که x در آرایه موجود نیست، این الگوریتم 6 مقایسه انجام می‌دهد (<math>log32+1=6</math>). در حالت کلی هر بار تعداد عناصر آرایه دو برابر شود، یک مرتبه به تعداد مقایسه‌ها افزوده خواهد شد. بر این اساس اگر n یکی از توان‌های 2 و x از همهٔ عناصر یک آرایهٔ n عنصری یزرگتر باشد، در جستجوی دودویی تعداد کل مقایسه‌ها از این رابطه حاصل می‌شود: <math>logn+1</math>.