Tìm nhỏ nhất trong mảng xoay có trùng lặp (Find Minimum in Rotated Sorted Array II) trong C++

Cho mảng đã sắp xếp rồi xoay tại pivot không biết. Mảng có thể có phần tử trùng lặp. Tìm phần tử nhỏ nhất.

Ví dụ

[4,5,5,5,6,8,2,3,4] → Min = 2.

Thuật toán: Binary Search biến thể

So sánh arr[low], arr[mid], arr[high]:

• arr[low] < arr[mid]: nửa trái đã sort, min ở nửa phải hoặc arr[low].
• arr[high] > arr[mid]: nửa phải đã sort, min ở arr[mid] hoặc nửa trái.
• arr[low] == arr[mid]: không xác định được, low++ (bỏ qua trùng lặp).
• arr[high] == arr[mid]: high--.

Lưu ý: Trường hợp xấu nhất (tất cả phần tử bằng nhau) → O(n).

Cài đặt 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 = INT_MAX;
        if (arr[low] < arr[mid]) {
            ans = min(arr[low], search(arr, mid, high));
        } else if (arr[high] > arr[mid]) {
            ans = min(arr[mid], search(arr, low, mid));
        } else if (arr[low] == arr[mid]) {
            ans = min(arr[low], search(arr, low + 1, high));
        } else if (arr[high] == arr[mid]) {
            ans = min(arr[high], search(arr, low, high - 1));
        }
        return ans;
    }

    int findMin(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.findMin(v);
    return 0;
}

Độ phức tạp

• Thời gian trung bình: O(log n).
• Thời gian xấu nhất: O(n) (khi nhiều phần tử trùng).
• Không gian: O(log n) stack đệ quy (hoặc O(1) nếu viết lặp).

Input / Output

Input:  [4,5,5,5,6,8,2,3,4]
Output: 2