এখানে আমরা দেখব কিভাবে একটি প্রদত্ত অ্যারেতে স্থির বিন্দু খুঁজে বের করা যায়। অ্যারেতে একটি উপাদানকে নির্দিষ্ট পয়েন্ট হিসাবে চিহ্নিত করা হবে যদি মানটি তার সূচকের মতো হয়। এই প্রোগ্রামটি মান প্রদান করবে যদি থাকে, অন্যথায় -1 ফেরত দেয়। অ্যারে নেতিবাচক সংখ্যাও ধারণ করতে পারে। এবং ডেটা উপাদানগুলি সাজানো হয়৷
৷এখানে আমরা O(log n) সময়ে এই সমস্যার সমাধান করতে বাইনারি অনুসন্ধান পদ্ধতি ব্যবহার করব। প্রথমেই আমরা পরীক্ষা করব যে মধ্যম উপাদানটি স্থির বিন্দু আছে কি না, যদি হ্যাঁ হয় তবে তা ফেরত দিব, যদি না হয়, তবে দুটি পরিস্থিতি হবে, যদি মধ্যম উপাদানটির সূচকটি সূচকে মানের থেকে বেশি হয়, যদি সূচকটি বড় হয়। , তারপর ডান দিকের স্থির বিন্দু পাওয়ার সুযোগ আছে, অন্যথায় বাম দিকে।
উদাহরণ
#include<iostream>
using namespace std;
int getFixedPoint(int arr[], int left, int right) {
if(right >= left){
int mid = (left + right)/2; /*low + (high - low)/2;*/
if(mid == arr[mid])
return mid;
if(mid > arr[mid])
return getFixedPoint(arr, (mid + 1), right);
else
return getFixedPoint(arr, left, (mid -1));
}
return -1;
}
int main() {
int arr[] = {-10, -1, 0, 3, 10, 11, 9, 50, 56};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"Fixed Point: "<< getFixedPoint(arr, 0, n-1);
} আউটপুট
Fixed Point: 3
