C++-এ সর্টেড বাইনারি অ্যারেতে ট্রানজিশন পয়েন্ট বের করা

শুধু ০ এবং ১ দিয়ে গঠিত একটি সর্টেড অ্যারে দেওয়া থাকলে, প্রথম '১' কত নাম্বার ইন্ডেক্সে আছে সেটা বের করতে হবে। এটাকে ট্রানজিশন পয়েন্ট বলে।

ইনপুট-১

N = 6, arr[] = {0,0,0,0,1,1}

আউটপুট

4

ইনপুট-২

N = 5, arr[] = {0,0,1,1,1}

আউটপুট

2

সমাধানের পদ্ধতি

বাইনারি সার্চ (Binary Search) ব্যবহার করে O(log n) সময়ে সমাধান করা যায়।

• low = 0, high = n-1 নিন।
• মিড পয়েন্ট বের করুন।
• যদি arr[mid] == 0 হয়, low = mid+1।
• যদি arr[mid] == 1 হয়, তবে চেক করুন এটি প্রথম ১ কিনা (আগের এলিমেন্ট ০ কিনা)। হ্যাঁ হলে ইন্ডেক্স রিটার্ন করুন, না হলে high = mid-1।
• না পাওয়া গেলে -1 রিটার্ন করুন।

উদাহরণ

#include <bits/stdc++.h>
using namespace std;

int transitionPoint(int *arr, int n) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (arr[mid] == 0)
            low = mid + 1;
        else if (arr[mid] == 1) {
            if (mid == 0 || (mid > 0 && arr[mid-1] == 0))
                return mid;
            high = mid - 1;
        }
    }
    return -1;
}

int main() {
    int n = 6;
    int arr[n] = {0,0,0,1,1,1};
    int ans = transitionPoint(arr, n);
    if (ans >= 0)
        cout << "Transition Point is: " << ans << endl;
    else
        cout << "Not Found" << endl;
    return 0;
}

আউটপুট

Transition Point is: 3