এখানে আমরা দেখব কিভাবে একটি প্রদত্ত অ্যারেতে স্থির বিন্দু খুঁজে বের করা যায়। অ্যারেতে একটি উপাদানকে নির্দিষ্ট পয়েন্ট হিসাবে চিহ্নিত করা হবে যদি মানটি তার সূচকের মতো হয়। এই প্রোগ্রামটি মান প্রদান করবে যদি থাকে, অন্যথায় -1 ফেরত দেয়। অ্যারে নেতিবাচক সংখ্যাও ধারণ করতে পারে। এবং তথ্য উপাদান বাছাই করা হয়. এখানে ডুপ্লিকেট উপাদানগুলি অ্যারেতে অনুমোদিত৷
৷এখানে আমরা O(log n) সময়ে এই সমস্যার সমাধান করতে বাইনারি অনুসন্ধান পদ্ধতি ব্যবহার করব। কিন্তু আমাদের কিছু পরিবর্তন দরকার, যদি সাধারণ বাইনারি অনুসন্ধান ব্যবহার করা হয়, তাহলে এটি সদৃশ উপাদানগুলির জন্য ব্যর্থ হতে পারে। বাম চেক করতে, আমাদের মিনিম (মধ্য – 1, মিড ভ্যালু) দিয়ে শুরু করতে হবে, এবং ডানদিকে চেক করতে, আমাদের সর্বোচ্চ (মিড + 1, মিড ভ্যালু) দিয়ে শুরু করতে হবে।
উদাহরণ
#include<iostream>
using namespace std;
int getFixedPoint(int arr[], int left, int right) {
if (right < left)
return -1;
int mid = (left + right) / 2;
int midValue = arr[mid];
if (mid == arr[mid])
return mid;
int leftindex = min(mid - 1, midValue);
int l = getFixedPoint(arr, left, leftindex);
if (l >= 0)
return l;
int rightindex = max(mid + 1, midValue);
int r = getFixedPoint(arr, rightindex, right);
return r;
}
int main() {
int arr[] = {-10, -5, 2, 2, 2, 3, 4, 7, 10, 12, 17};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"Fixed Point: "<< getFixedPoint(arr, 0, n-1);
} আউটপুট
Fixed Point: 2
