সর্টেড 0/1 অ্যারেতে প্রথম ১-এর ইনডেক্স বের করা (C++)

সমস্যা বিবরণ

একটি সর্টেড বাইনারি অ্যারে (শুধু ০ ও ১) দেওয়া আছে। আমাদের কাজ হল প্রথম ১-এর ইনডেক্স বের করা।

উদাহরণ

ইনপুট: {0,0,0,1,1}
আউটপুট: 3

পদ্ধতি ১: লিনিয়ার সার্চ (O(n))

সरलভাবে ০ থেকে n-1 পর্যন্ত লুপ করে প্রথম ১ খুঁজা।

পদ্ধতি ২: বাইনারি সার্চ (O(log n)) - সেরা

মিডেল ভ্যালু ১ হলে বামে খোঁজা, ০ হলে ডানে খোঁজা।

#include <iostream>
using namespace std;

int firstOne(int bin[], int n){
    int lo=0, hi=n-1;
    while(lo<=hi){
        int mid=(lo+hi)/2;
        if(bin[mid]==1 && (mid==0 || bin[mid-1]==0)) return mid;
        else if(bin[mid]==1) hi=mid-1;
        else lo=mid+1;
    }
    return -1;
}

int main(){
    int bin[]={0,0,0,1,1,1,1};
    cout << firstOne(bin,7); // 3
    return 0;
}