ปัญหา
หาจุดคงที่ในอาร์เรย์ที่จัดเรียงแล้ว (ไม่มีค่าซ้ำ) โดยจุดคงที่คือสมาชิกที่ค่าเท่ากับดัชนีของมัน
ตัวอย่าง: arr = [-10, -1, 0, 3, 10, 11, 9, 50, 56] จุดคงที่คือ 3 (arr[3] = 3)
วิธีแก้ปัญหา: Binary Search มาตรฐาน
เนื่องจากอาร์เรย์จัดเรียงแล้วและไม่มีค่าซ้ำ ใช้ Binary Search ธรรมดา:
- ถ้า mid == arr[mid] พบคำตอบ
- ถ้า mid > arr[mid] จุดคงที่อยู่ทางขวา (ค้นหา mid+1 ถึง right)
- ถ้า mid < arr[mid] จุดคงที่อยู่ทางซ้าย (ค้นหา left ถึง mid-1)
ความซับซ้อนเวลา: O(log n)
ตัวอย่างโค้ด C++
#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 << "Fixed Point: " << getFixedPoint(arr, 0, n-1);
return 0;
}
ผลลัพธ์
Fixed Point: 3
