Binary Search

Sorted list-এ একটা মান খুঁজুন, প্রতিবার list-এর অর্ধেক বাদ দিয়ে।

The idea (like guessing a number)

ধরুন আমি 1 থেকে 100-এর মধ্যে একটা সংখ্যা ভেবেছি। আপনি বললেন 50। আমি বললাম “আরও বড়”। এখন আপনি জানেন সংখ্যাটা 51–100-এর মধ্যে, অর্থাৎ এক guess-এই অর্ধেক সংখ্যা বাদ। এরপর 75 বললেন, উত্তর “আরও ছোট”… এভাবে মোটামুটি 7 বারের মধ্যেই সবসময় পেয়ে যাবেন। Binary search ঠিক এভাবেই কাজ করে: মাঝখানের মান দেখুন, তারপর যে অর্ধেকে উত্তর থাকতে পারে না সেটা বাদ দিন।

এটা শুধু sorted list-এ কাজ করে। list-এর size দ্বিগুণ হলে মাত্র এক ধাপ বাড়ে: 1,000,000টা item-এ লাগে প্রায় 20 ধাপ।

Run করে দেখুন

নিজে চেষ্টা করুন

সাধারণ ভুল