Phần tử lớn nhất trong mảng đã sắp xếp và xoay trong C++

Mô tả

Cho mảng đã sắp xếp các phần tử phân biệt, bị xoay tại điểm không xác định. Nhiệm vụ: tìm phần tử lớn nhất.

Ví dụ

Mảng: {30, 40, 50, 10, 20} → Phần tử lớn nhất = 50

Thuật toán (Tìm kiếm nhị phân - O(log n))

• Phần tử lớn nhất là phần tử duy nhất có phần tử kế tiếp nhỏ hơn nó. Nếu không có phần tử kế tiếp nhỏ hơn → không bị xoay → phần tử cuối là lớn nhất
• Kiểm tra điều kiện tại phần tử giữa (mid) so với mid-1 và mid+1
• Nếu max không ở giữa:
  • Nếu phần tử giữa > phần tử cuối → max nằm nửa trái
  • Ngược lại → max nằm nửa phải

Chương trình C++

#include <bits/stdc++.h> 
using namespace std; 

int getMaxinSortedAndRotated(int *arr, int low, int high) {
    if (high < low) return arr[0];
    if (high == low) return arr[high];
    
    int mid = low + (high - low) / 2;
    
    if (mid < high && arr[mid + 1] < arr[mid])
        return arr[mid];
    if (mid > low && arr[mid] < arr[mid - 1])
        return arr[mid - 1];
    
    if (arr[low] > arr[mid])
        return getMaxinSortedAndRotated(arr, low, mid - 1);
    else
        return getMaxinSortedAndRotated(arr, mid + 1, high);
}

int main() {
    int arr[] = {30, 40, 50, 10, 20};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum element = " << getMaxinSortedAndRotated(arr, 0, n - 1) << endl;
    return 0;
}

Kết quả

Maximum element = 50

Lưu ý

Code gốc có lỗi typo tên hàm (getMaxinSortedAndRorated vs getMaxinSortedAndRoratrr). Đã sửa trong phiên bản trên.