جستجوی باینری

جستجوی باینری یک — تخمین پیچیدگی آن O(log2(n)) است، در حالی که جستجوی متوالی مرسوم دارای O(n) است. به این معنی که مثلا برای یک آرایه از 1024 عنصر، یک جستجوی خطی، در بدترین حالت، زمانی که عنصر مورد نظر در آرایه نباشد، تمام 1024 عنصر را پردازش می کند. جستجوی باینری برای پردازش عناصر \(log_2(1024) = 10\) کافی است. این نتیجه به این دلیل به دست می‌آید که پس از مرحله اول حلقه، ناحیه جستجو به 512 عنصر کاهش می‌یابد، پس از – تا 256 و غیره.

پیاده سازی

خداحافظ (راست – چپ > 1)  // تا زمانی که حاشیه سمت راست در سمت راست سمت چپ باشد
nc
  وسط = (سمت چپ + سمت راست) /< /span> 2; // وسط ناحیه جستجو
  اگر (A[middle] >= ب) سپس
    سمت راست = middle; // حاشیه سمت راست را حرکت دهید
  در غیر این صورت
    چپ = وسط; // در غیر این صورت حاشیه سمت چپ را حرکت دهید
سی سی
اگر (A[right] == X) سپس
  خروجی درست؛
در غیر این صورت
  خروجی -1;