यहां हम देखेंगे कि किसी दिए गए सरणी में निश्चित बिंदु कैसे खोजें। सरणी में एक तत्व को निश्चित बिंदु के रूप में दर्शाया जाएगा यदि मान उसके सूचकांक के समान है। यदि कोई है तो यह प्रोग्राम मान लौटाएगा, अन्यथा -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