Sorted list-এ একটা মান খুঁজুন, প্রতিবার list-এর অর্ধেক বাদ দিয়ে।
ধরুন আমি 1 থেকে 100-এর মধ্যে একটা সংখ্যা ভেবেছি। আপনি বললেন 50। আমি বললাম “আরও বড়”। এখন আপনি জানেন সংখ্যাটা 51–100-এর মধ্যে, অর্থাৎ এক guess-এই অর্ধেক সংখ্যা বাদ। এরপর 75 বললেন, উত্তর “আরও ছোট”… এভাবে মোটামুটি 7 বারের মধ্যেই সবসময় পেয়ে যাবেন। Binary search ঠিক এভাবেই কাজ করে: মাঝখানের মান দেখুন, তারপর যে অর্ধেকে উত্তর থাকতে পারে না সেটা বাদ দিন।
এটা শুধু sorted list-এ কাজ করে। list-এর size দ্বিগুণ হলে মাত্র এক ধাপ বাড়ে: 1,000,000টা item-এ লাগে প্রায় 20 ধাপ।
91 (শেষ item) আর 2 (প্রথম item) খুঁজুন। প্রতিটায় কত ধাপ লাগে?40 খুঁজুন। শেষে lo আর hi-এর মান কী দাঁড়ায়?mid দেখা হয়ে গেলে mid+1 বা mid-1-এ যান, mid-এ নয়। নইলে loop কখনো শেষ নাও হতে পারে।mid := lo + (hi-lo)/2 লিখুন, (lo+hi)/2 নয়। index অনেক বড় হলে দ্বিতীয়টায় overflow হতে পারে।