Trong chương trình C++ này, chúng ta sẽ tìm một trong các phần tử đỉnh (peak element) của mảng bằng cách sử dụng phương pháp tìm kiếm nhị phân. Thuật toán này trả về phần tử đỉnh đầu tiên tìm được với độ phức tạp thời gian O(log n).
Thuật toán
Bắt đầu Hàm PeakElement() nhận vào mảng 'arr', chỉ số bắt đầu và chỉ số kết thúc. Tính chỉ số giữa (mid) của đoạn mảng con. Nếu mid nằm ở biên và giá trị tại mid lớn hơn hàng xóm thì trả về mid là đỉnh. Nếu giá trị tại mid lớn hơn cả hai hàng xóm thì trả về mid là đỉnh. Nếu giá trị bên phải mid lớn hơn mid thì đệ quy gọi PeakElement() với nửa sau của mảng. Nếu giá trị bên trái mid lớn hơn mid thì đệ quy gọi PeakElement() với nửa trước của mảng. Kết thúc
Mã ví dụ
#include <iostream>
using namespace std;
int PeakElement(int a[], int start, int end) {
int mid;
mid = (end + start + 1) / 2;
if ((a[mid] > a[mid+1] && mid == start) || (a[mid] > a[mid-1] && mid == end)) {
return a[mid];
} else if (a[mid] < a[mid-1] && a[mid] > a[mid+1]) {
return a[mid];
} else if (a[mid] <= a[mid+1]) {
return PeakElement(a, mid+1, end);
} else if (a[mid] <= a[mid-1]) {
return PeakElement(a, start, mid-1);
}
}
int main() {
int n, i, p;
cout << "\nNhập số lượng phần tử dữ liệu: ";
cin >> n;
int arr[n];
for (i = 0; i < n; i++) {
cout << "Nhập phần tử " << i+1 << ": ";
cin >> arr[i];
}
p = PeakElement(arr, 0, n-1);
cout << "\nPhần tử đỉnh của mảng đã cho là: " << p;
return 0;
}
Kết quả
Nhập số lượng phần tử dữ liệu: 5 Nhập phần tử 1: 45 Nhập phần tử 2: 26 Nhập phần tử 3: 70 Nhập phần tử 4: 60 Nhập phần tử 5: 15 Phần tử đỉnh của mảng đã cho là: 70