ที่นี่เราจะมาดูวิธีค้นหาจุดคงที่ในอาร์เรย์ที่กำหนด ในอาร์เรย์หนึ่งองค์ประกอบจะถูกแสดงเป็นจุดคงที่หากค่าเหมือนกับดัชนี โปรแกรมนี้จะคืนค่าถ้ามี มิฉะนั้นจะคืนค่า -1 อาร์เรย์สามารถเก็บตัวเลขติดลบได้เช่นกัน และองค์ประกอบข้อมูลจะถูกจัดเรียง อนุญาตให้ใช้องค์ประกอบที่ซ้ำกันในอาร์เรย์ได้
เราจะใช้วิธีการค้นหาแบบไบนารีเพื่อแก้ปัญหานี้ในเวลา O(log n) แต่เราต้องการการปรับเปลี่ยนบางอย่าง หากใช้การค้นหาแบบไบนารีปกติ อาจทำให้องค์ประกอบที่ซ้ำกันล้มเหลว ในการตรวจสอบด้านซ้าย เราต้องเริ่มจากค่าต่ำสุด (กลาง – 1, ค่ากลาง) และการตรวจสอบทางขวา เราต้องเริ่มจากค่าสูงสุด (กลาง + 1, ค่ากลาง)
ตัวอย่าง
#include<iostream>
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);
} ผลลัพธ์
Fixed Point: 2
