বাইনারি সার্চ ও এর ভ্যারিয়েন্ট

১ · বাইনারি সার্চ — সংক্ষিপ্ত রিক্যাপ

বাইনারি সার্চের মেকানিক্স (একটি সর্টেড অ্যারেতে মাঝের এলিমেন্টের সাথে তুলনা করে অর্ধেক অংশ বাতিল করা) ইতিমধ্যে DSA কোর্সে কভার করা হয়েছে। L14-এর D&C টেমপ্লেটে এটি একটি বিশেষ কেস — ডিভাইড ধাপেই সিদ্ধান্ত নেওয়া হয়ে যায় কোন অর্ধেকে উত্তর থাকতে পারে, কনকার ধাপে শুধু একটি সাব-প্রবলেম রিকার্সিভভাবে সমাধান করা হয় (অন্যটি সম্পূর্ণ বাতিল), এবং কমবাইন ধাপে কিছুই করার থাকে না।

২ · রিকারেন্স ডেরিভেশন — $\Theta(\log n)$

প্রতিটি ধাপে (মাঝের এলিমেন্টের সাথে একটি তুলনা, $O(1)$) অ্যারের আকার অর্ধেক হয়ে যায় এবং মাত্র একটি সাব-প্রবলেম রিকার্সিভভাবে সমাধান করতে হয় ($a = 1$)। তাই রিকারেন্স:

মাস্টার থিওরেম প্রয়োগ করতে ($a=1$, $b=2$, $f(n) = \Theta(1)$): $n^{\log_b a} = n^{\log_2 1} = n^0 = 1$। যেহেতু $f(n) = \Theta(1) = \Theta(n^{\log_b a})$ ($k=0$ সহ), এটি কেস ২-এর সাথে মেলে (L13 দ্রষ্টব্য):

একই ফলাফল সরাসরি আনরোল (unroll) করেও পাওয়া যায়: $k$ বার অর্ধেক করার পর আকার দাঁড়ায় $n/2^k$; এটি $1$-এ পৌঁছায় যখন $2^k = n$, অর্থাৎ $k = \log_2 n$। প্রতিটি ধাপে $O(1)$ কাজ হলে মোট কাজ $O(\log n)$।

৩ · ভ্যারিয়েন্ট — Leftmost Occurrence ও Insertion Point

স্ট্যান্ডার্ড বাইনারি সার্চ শুধু বলে "target আছে কি না, থাকলে কোনো একটি ইনডেক্সে"। কিন্তু অ্যারেতে ডুপ্লিকেট থাকলে (যেমন [2, 4, 4, 4, 4, 7]-এ target $= 4$), স্ট্যান্ডার্ড সংস্করণ ইনডেক্স $2$, $3$, বা $4$ — যেকোনো একটি ফেরত দিতে পারে (কোন ইনডেক্সটি "মাঝে" পড়ে তার উপর নির্ভর করে)। বাস্তব প্রয়োগে প্রায়ই নির্দিষ্টভাবে প্রথম (leftmost) অকারেন্স দরকার হয়।

সমাধান সহজ: match পেলেও সাথে সাথে না থেমে, বাম দিকেও আরও ছোট কোনো match আছে কি না খুঁজতে থাকা — অর্থাৎ যখন arr[mid] == target, তখনও ডান সীমানা mid-এ নামিয়ে বাম দিকে সার্চ চালিয়ে যাওয়া, right অর্ধেক পুরোপুরি বাদ দেওয়া নয়। এই একই কৌশল দিয়ে insertion pointও বের করা যায় — অর্থাৎ target-কে অ্যারেতে বসালে সর্টেড ক্রম বজায় রাখতে সবচেয়ে-বাম কোন ইনডেক্সে বসাতে হবে (Python-এর bisect.bisect_left ঠিক এই কাজটিই করে)। আসলে leftmost occurrence আর insertion point একই ফাংশনের দুটি ব্যবহার: idx = insertion_point(arr, target); যদি arr[idx] == target হয় তবে সেটাই leftmost occurrence, নাহলে target অ্যারেতে নেই কিন্তু idx এখনও বৈধ insertion point।

৪ · কম্পিউটেশনাল যাচাই — নেইভ স্ক্যান ও stdlib bisect-এর বিরুদ্ধে

নিচের কোডে কাস্টম bisect_left_custom (insertion point) ও তার উপর ভিত্তি করে leftmost_occurrence ইমপ্লিমেন্ট করা হয়েছে। এগুলো দুটি ভিন্ন গ্রাউন্ড-ট্রুথের বিরুদ্ধে যাচাই করা হয়েছে — Python-এর নিজস্ব bisect.bisect_left (stdlib) এবং একটি নেইভ লিনিয়ার স্ক্যান — বহু র‍্যান্ডম টেস্ট কেসে, যার মধ্যে ডুপ্লিকেট-সহ ও খালি অ্যারেও আছে।

import random
import bisect

def bisect_left_custom(arr, target):
    """target ঢোকানোর সবচেয়ে-বাম বৈধ ইনডেক্স (bisect.bisect_left-এর মতোই)।"""
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = (lo + hi) // 2
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo

def binary_search_standard(arr, target):
    """স্ট্যান্ডার্ড বাইনারি সার্চ: target-এর যেকোনো একটি ইনডেক্স, নাহলে -1।"""
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

def leftmost_occurrence(arr, target):
    """প্রথম অকারেন্সের ইনডেক্স, নাহলে -1।"""
    idx = bisect_left_custom(arr, target)
    if idx < len(arr) and arr[idx] == target:
        return idx
    return -1

def linear_search_leftmost(arr, target):
    """নেইভ বেসলাইন: বাম থেকে ডানে স্ক্যান করে প্রথম মিল খুঁজে বের করা।"""
    for i, x in enumerate(arr):
        if x == target:
            return i
    return -1

random.seed(42)
trials = 300
bisect_matches = 0
leftmost_matches = 0
standard_correct = 0

for _ in range(trials):
    n = random.randint(0, 20)
    arr = sorted(random.randint(0, 10) for _ in range(n))   # ডুপ্লিকেট-সহ সর্টেড অ্যারে
    target = random.randint(-2, 12)                          # কিছু target অ্যারের বাইরে

    if bisect_left_custom(arr, target) == bisect.bisect_left(arr, target):
        bisect_matches += 1

    if leftmost_occurrence(arr, target) == linear_search_leftmost(arr, target):
        leftmost_matches += 1

    idx = binary_search_standard(arr, target)
    present_actual = target in arr
    if idx == -1:
        standard_correct += int(not present_actual)
    else:
        standard_correct += int(0 <= idx < len(arr) and arr[idx] == target)

print(f"মোট টেস্ট: {trials}")
print(f"bisect_left_custom বনাম stdlib bisect.bisect_left মিলেছে: {bisect_matches}/{trials}")
print(f"leftmost_occurrence বনাম নেইভ লিনিয়ার স্ক্যান মিলেছে: {leftmost_matches}/{trials}")
print(f"binary_search_standard সঠিক ফলাফল দিয়েছে: {standard_correct}/{trials}")

assert bisect_matches == trials
assert leftmost_matches == trials
assert standard_correct == trials
print("\nসব টেস্ট পাস করেছে")