Tìm điểm cố định (giá trị bằng chỉ số) trong mảng C++

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

Giải thuật

Sử dụng tìm kiếm nhị phân chuẩn O(log n). So sánh mid với arr[mid]: nếu bằng nhau trả về mid. Nếu mid > arr[mid], tìm bên phải (mid+1, right). Ngược lại tìm bên trái (left, mid-1).

Ví dụ minh họa

#include <iostream>
using namespace std;

int getFixedPoint(int arr[], int left, int right) {
    if (right >= left) {
        int mid = (left + right) / 2;
        if (mid == arr[mid]) return mid;
        if (mid > arr[mid])
            return getFixedPoint(arr, mid + 1, right);
        else
            return getFixedPoint(arr, left, mid - 1);
    }
    return -1;
}

int main() {
    int arr[] = {-10, -1, 0, 3, 10, 11, 9, 50, 56};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Diem co dinh: " << getFixedPoint(arr, 0, n-1);
}

Kết quả

Diem co dinh: 3