Chương trình tìm số lớn nhất trong mảng đã xoay (rotated array) trong C++

Cho mảng đã sắp xếp rồi xoay tại một điểm pivot không biết. Tìm phần tử lớn nhất.

Ví dụ: [3,4,5,1,2] → 5. Mảng có thể chứa phần tử trùng lặp.

Thuật toán (Tìm kiếm nhị phân biến thể)

• Dùng đệ quy/iterative với low, high.
• Tính mid. So sánh arr[low], arr[mid], arr[high] để quyết định nửa nào chứa max.
• Xử lý trường hợp bằng nhau bằng cách thu hẹp khoảng tìm kiếm.

Ví dụ triển khai (C++)

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

class Solution {
public:
    int search(vector<int>& arr, int low, int high) {
        if (low == high) return arr[low];
        int mid = low + (high - low) / 2;
        int ans = 0;
        if (arr[low] < arr[mid])
            ans = max(arr[low], search(arr, mid, high));
        else if (arr[high] > arr[mid])
            ans = max(arr[mid], search(arr, low, mid));
        else if (arr[low] == arr[mid])
            ans = max(arr[low], search(arr, low + 1, high));
        else
            ans = max(arr[high], search(arr, low, high - 1));
        return ans;
    }
    int findMax(vector<int>& nums) {
        return search(nums, 0, nums.size() - 1);
    }
};

int main() {
    Solution ob;
    vector<int> v = {4,5,5,5,6,8,2,3,4};
    cout << ob.findMax(v);
    return 0;
}

Đầu vào

[4,5,5,5,6,8,2,3,4]

Đầu ra

8