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