หาจุดคงที่ในอาร์เรย์ที่อนุญาตให้มีค่าซ้ำ C++

ปัญหา

หาจุดคงที่ (Fixed Point) ในอาร์เรย์ที่จัดเรียงแล้ว โดยจุดคงที่คือสมาชิกที่มีค่าเท่ากับดัชนี (index) ของมัน อาร์เรย์อาจมีค่าลบและอนุญาตให้มีค่าซ้ำได้

ตัวอย่าง: arr = [-10, -5, 2, 2, 2, 3, 4, 7, 10, 12, 17] จุดคงที่คือ 2 (arr[2] = 2)

วิธีแก้ปัญหา: Binary Search แบบปรับเปลี่ยน

Binary Search ปกติอาจล้มเหลวเมื่อมีค่าซ้ำ ต้องปรับเปลี่ยนดังนี้:

• ถ้า mid == arr[mid] พบคำตอบแล้ว
• ด้านซ้าย: ค้นหาจาก left ถึง min(mid - 1, midValue)
• ด้านขวา: ค้นหาจาก max(mid + 1, midValue) ถึง right

ความซับซ้อนเวลา: O(log n)

ตัวอย่างโค้ด C++

#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 << "Fixed Point: " << getFixedPoint(arr, 0, n-1);
    return 0;
}

ผลลัพธ์

Fixed Point: 2