Binary search কীভাবে কাজ করে এবং এটির জন্য কী প্রয়োজন?

Question

Accepted Answer

**Binary search** একটি **sorted** array তে একটি target খুঁজে পায় search range কে বারবার অর্ধেক করে। প্রতিটি comparison অবশিষ্ট উপাদানগুলির অর্ধেক দূর করে, যা **O(log n)** সময় দেয়। ## The idea মধ্য উপাদানটি দেখুন। যদি এটি target এর সমান হয়, সম্পন্ন। যদি target ছোট হয়, বাম অর্ধ অনুসন্ধান করুন; যদি বড় হয়, ডান অর্ধ অনুসন্ধান করুন। যতক্ষণ না পাওয়া যায় বা range খালি না হয় ততক্ষণ পুনরাবৃত্তি করুন। ## Example ```python def binary_search(arr, target): lo, hi = 0, len(arr) - 1 while lo <= hi: mid = (lo + hi) // 2 # middle index if arr[mid] == target: return mid # found it elif arr[mid] < target: lo = mid + 1 # discard left half else: hi = mid - 1 # discard right half return -1 # not present binary_search([1, 3, 5, 7, 9], 7) # -> 3 ``` ## Trace ```text Search 7 in [1,3,5,7,9] lo=0 hi=4 mid=2 -> 5 < 7 => lo=3 lo=3 hi=4 mid=3 -> 7 == 7 => return 3 ``` ## Complexity - **Time:** O(log n). **Space:** O(1) iterative। ## Pitfalls **input অবশ্যই sorted হতে হবে** — অন্যথায় ফলাফল অর্থহীন। `lo`/`hi` এ off-by-one bugs সাবধানে দেখুন এবং কিছু ভাষায় integer overflow সাবধানে দেখুন (use `lo + (hi-lo)//2`)। ## Why it matters Search space কে অর্ধেক করা একটি মিলিয়ন-উপাদান lookup কে ~20 comparisons এ পরিণত করে। এর পিছনের divide-and-conquer প্যাটার্ন trees, databases, এবং অসংখ্য interview problems এ পুনরায় উপস্থিত হয়। এর একটি কঠিন প্রয়োজনীয়তা জানা — sorted input — আপনাকে একটি ক্লাসিক সূক্ষ্ম bug থেকে রক্ষা করে।