Tìm điểm cố định trong mảng cho phép trùng lặp C++

Điểm cố định trong mảng là phần tử có giá trị bằng chỉ số của nó (arr[i] = i). Mảng đã sắp xếp, có thể chứa số âm và phần tử trùng lặp. Trả về chỉ số điểm cố định hoặc -1 nếu không có.

Giải thuật

Sử dụng tìm kiếm nhị phân biến đổi để xử lý phần tử trùng lặp. Nếu mid == arr[mid] trả về mid. Để tìm bên trái, dùng min(mid-1, arr[mid]). Để tìm bên phải, dùng max(mid+1, arr[mid]). Độ phức tạp O(log n).

Ví dụ minh họa

#include <iostream>
#include <algorithm>
using namespace std;

int getFixedPoint(int arr[], int left, int right) {
    if (right < left) return -1;
    int mid = (left + right) / 2;
    int midValue = arr[mid];
    
    if (mid == arr[mid]) return mid;
    
    int leftindex = min(mid - 1, midValue);
    int l = getFixedPoint(arr, left, leftindex);
    if (l >= 0) return l;
    
    int rightindex = max(mid + 1, midValue);
    int r = getFixedPoint(arr, rightindex, right);
    return r;
}

int main() {
    int arr[] = {-10, -5, 2, 2, 2, 3, 4, 7, 10, 12, 17};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Diem co dinh: " << getFixedPoint(arr, 0, n-1);
}

Kết quả

Diem co dinh: 2