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

সমস্যা বিবরণ

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

উদাহরণ

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

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

ইনডেক্স ০ থেকে শুরু করে ১ পাওয়া পর্যন্ত চলা।

পদ্ধতি ২: এক্সপোনেনশিয়াল সার্চ + বাইনারি সার্চ (O(log index)) - সেরা

হাই বাউন্ড ১, ২, ৪, ৮... ডাবল করে ১ পাওয়া পর্যন্ত বেড়ানো। তারপর সেই রেঞ্জে বাইনারি সার্চ।

#include <iostream>
using namespace std;

int firstOneInfinite(int bin[], int low, int high){
    while(low<=high){
        int mid=(low+high)/2;
        if(bin[mid]==1 && (mid==0 || bin[mid-1]==0)) return mid;
        else if(bin[mid]==1) high=mid-1;
        else low=mid+1;
    }
    return -1;
}

int main(){
    int bin[]={0,0,0,1,1,1,1};
    int low=0, high=1;
    while(bin[high]!=1){ low=high; high*=2; }
    cout << firstOneInfinite(bin,low,high); // 3
    return 0;
}