資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理
社會研究
時尚研究
法律研究在允許重複項的陣列中找出固定點 (C++)
在本文中，我們將瞭解如何在給定陣列中找出固定點。如果陣列中的元素值與其索引相同，則該元素會被標記為固定點。此程式將在存在固定點時返回該值，否則返回 -1。陣列還可以容納負數。並且資料元素是有序的。此處的陣列中允許出現重複元素。
我們將在 O(log n) 時間內使用二分查詢方法來解決此問題。但我們需要進行一些修改，如果使用普通的二分查詢，則對於重複元素，它可能會失敗。要檢查左側，我們必須從 min(mid – 1, midValue) 開始，要檢查右側，我們必須從 max(mid + 1, midValue) 開始。
示例
#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
更新日期: 2019-10-24
126 次瀏覽
廣告