資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法學在 C++ 中查詢先遞增後遞減陣列中的最大元素
假設我們有一個數組，它先遞增後遞減。我們必須找到陣列中的最大值。所以如果陣列元素類似 A = [8, 10, 20, 80, 100, 250, 450, 100, 3, 2, 1]，則輸出將為 450。
我們可以使用二分查詢來解決這個問題。有三種情況：
- 當中間元素大於其兩個相鄰元素時，則中間元素為最大值。
- 如果中間元素大於下一個元素，但小於前一個元素，則最大值位於中間元素的左側。
- 如果中間元素小於下一個元素，但大於前一個元素，則最大值位於中間元素的右側。
示例
#include<iostream>
using namespace std;
int getMaxElement(int array[], int left, int right) {
if (left == right)
return array[left];
if ((right == left + 1) && array[left] >= array[right])
return array[left];
if ((right == left + 1) && array[left] < array[right])
return array[right];
int mid = (left + right)/2;
if ( array[mid] > array[mid + 1] && array[mid] > array[mid - 1])
return array[mid];
if (array[mid] > array[mid + 1] && array[mid] < array[mid - 1])
return getMaxElement(array, left, mid-1);
else
return getMaxElement(array, mid + 1, right);
}
int main() {
int array[] = {8, 10, 20, 80, 100, 250, 450, 100, 3, 2, 1};
int n = sizeof(array)/sizeof(array[0]);
cout << "The maximum element is: " << getMaxElement(array, 0, n-1);
}輸出
The maximum element is: 450
更新於：2019年12月17日
245 次瀏覽
廣告