کارآیی_الگوریتمی
در الگوریتم جستجوی ترتیبی برای یافتن عنصر مشخص x در آرایه، از ابتدای آرایه آغاز کرده و به ترتیب یکی یکی عناصر را با آن مقایسه می‌کنیم. هرکدام که با عنصر x برابر بود، مکان همان عنصر را در آرایه بعنوان جواب معرفی کرده و در صورت عدم وجود عنصر x عدد صفر را بعنوان خروجی الگوریتم معرفی می‌کنیم. یک الگوریتم جستجوی ترتیبی به صورت زیر است: void seqsearch (int n,           const keytype S[],            keytype x,            index& location) {    location = 1; While (location<=n &&  S[location]!=x) location ++; if (location> n)        location = 0; }اما در الگوریتم جستجوی دودویی روش کار به این صورت است که ابتدا عنصر x را با عنصر میانی آرایه مقایسه می‌کنیم، اگر برابر بودند به جواب رسیده‌ایم و اگر نه دو حالت روی خواهد داد. یا x کوچکتر از عنصر میانی است که در چنین حالتی در صورت وجود باید در نیمهٔ اول آرایه باشد. لذا با همین روال جستجو را برای نیمهٔ اول انجام می‌دهیم. (اگر x با عنصر میانی نیمهٔ اول برابر بود به جواب رسیده‌ایم و تا انتها همینطور ادامه می‌دهیم.) و یا x بزرگتر از عنصر میانی است که در این صورت در نیمهٔ دوم آرایه جستجو را انجام می‌دهیم. به همین ترتیب جستجو را تا جایی ادامه می‌دهیم که به x برسیم یا اگر تا انتها پیدا نشد عدد صفر را بعنوان خروجی آرایه معرفی می‌کنیم. یک الگوریتم جستجوی دودویی در زیر آمده‌است: void binsearch (int n,           const keytype S[],            keytype x,            index& location) {  index low, high, mid; low = 1; high = n;  location = 0; while (low <= high && location = 0) { mid =[ (low + high)/2 ]; if (x == S[mid]) location = mid; else if (x <S[mid]) high = mid – 1; else low = mid + 1; } }حال برای مقایسهٔ کارایی این دو لازم است که تعداد مقایسه‌های انجام شده توسط هر یک از این دو الگوریتم را به‌طور مثال به ازای ورودی‌های خاص و مشترک برای این دو بدست آوریم. برای این کار مثلاً فرض می‌کنیم که تعداد عناصر آرایهٔ S برابر ۱۶ بوده و عدد x در آرایه نباشد. در این صورت الگوریتم جستجوی ترتیبی ۱۶ مقایسه انجام داده و سپس اعلام می‌کند که x در آرایه موجود نیست و در حالت کلی نیز همواره در بدترین حالت (زمانی که x در آرایه موجود نباشد) تعداد مقایسات در این الگوریتم برابر n (تعداد عناصر آرایه) خواهد بود. (در صورت وجود x در آرایه تعداد مقایسه‌ها کمتر خواهد بود). و در الگوریتم جستجوی دودویی در حالتی که x در آرایه موجود نباشد، در هر حلقهٔ while دو بار عدد x با S[mid] مقایسه می‌شود. اما در واقع اگر اجرایی کارا از الگوریتم توسط اسمبلر صورت گیرد در هر بار اجرای حلقهٔ while تنها یک بار x با S[mid] مقایسه می‌شود. در نتیجهٔ این مقایسه حالت مناسب بر اساس مقدار کد شرط تعیین می‌شود. با فرض اینکه الگوریتم جستجوی دودویی از این روش استفاده می‌کند، برای جستجوی عدد x در همان آرایهٔ ۱۶ عنصری که x از همهٔ عناصر آرایه بزرگتر است، این الگوریتم فقط ۵ مقایسه انجام می‌دهد که log16+1=5 است (منظور، لگاریتم در مبنای 2 می‌باشد). و البته این بیشترین تعداد مقایسه هاست که با این روش صورت می‌گیرد. (در صورتی که x در آرایه موجود باشد تعداد مقایسه‌ها بیشتر نخواهد بود). حال اگر تعداد عناصر آرایه دو برابر شود یعنی 32 عنصر داشته باشیم، تعداد مقایسات در الگوریتم جستجوی دودویی فقط ۱ مرتبه از حالت قبل بیشتر خواهد بود، یعنی زمانی که اولین مقایسه صورت می‌گیرد و آرایه به دو زیر آرایه تقسیم می‌شود. لذا باز هم در بدترین حالت که x در آرایه موجود نیست، این الگوریتم 6 مقایسه انجام می‌دهد (log32+1=6). در حالت کلی هر بار تعداد عناصر آرایه دو برابر شود، یک مرتبه به تعداد مقایسه‌ها افزوده خواهد شد. بر این اساس اگر n یکی از توان‌های 2 و x از همهٔ عناصر یک آرایهٔ n عنصری یزرگتر باشد، در جستجوی دودویی تعداد کل مقایسه‌ها از این رابطه حاصل می‌شود: logn+1. در نتیجه زمانی که x از همهٔ عناصر آرایه بزرگتر باشد تعداد مقایسه‌ها در الگوریتم جستجوی دودویی نسبت به الگوریتم جستجوی ترتیبی به ویژه برای مقادیر بزرگ n به مقدار قابل توجهی کمتر خواهد بود. برای نمونه برای n=128 تعداد مقایسه‌ها در جستجوی ترتیبی برابر 128 بوده و در جستجوی دودویی 8 می‌باشد. و برای n=1024 در جستجوی ترتیبی تعداد مقایسه‌ها برابر 1024 بوده و در جستجوی دودویی تنها 9 مقایسه انجام می‌شود. و برای مقادیر بزرگتر n این اختلاف به مراتب بیشتر و چشمگیرتر خواهد بود.