Giả sử chúng ta có một mảng, ban đầu đang tăng sau đó giảm dần. Chúng ta phải tìm giá trị lớn nhất trong mảng. Vì vậy, nếu các phần tử của mảng giống như A =[8, 10, 20, 80, 100, 250, 450, 100, 3, 2, 1], thì đầu ra sẽ là 500.
Chúng ta có thể sử dụng tìm kiếm nhị phân để giải quyết vấn đề này. Có ba điều kiện -
- Khi giá trị giữa lớn hơn cả hai phần tử liền kề của nó, thì giá trị giữa là cực đại
- Nếu giá trị giữa lớn hơn phần tử tiếp theo nhưng nhỏ hơn phần tử trước đó thì giá trị tối đa nằm ở bên trái của phần tử giữa.
- Nếu phần tử ở giữa nhỏ hơn phần tử tiếp theo nhưng lớn hơn phần tử trước đó, thì giá trị tối đa nằm ở phía bên phải của phần tử giữa.
Ví dụ
#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);
} Đầu ra
The maximum element is: 450