資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究在 C++ 中查詢給定陣列中的固定點（值等於索引）
在這裡，我們將瞭解如何在給定陣列中查詢固定點。在陣列中，如果一個元素的值與其索引相同，則將其稱為固定點。此程式將返回任何值（如果存在），否則返回 -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
更新於: 2019-10-24
191 次檢視
廣告