ที่นี่เราจะมาดูวิธีค้นหาจุดคงที่ในอาร์เรย์ที่กำหนด ในอาร์เรย์หนึ่งองค์ประกอบจะถูกแสดงเป็นจุดคงที่หากค่าเหมือนกับดัชนี โปรแกรมนี้จะคืนค่าถ้ามี มิฉะนั้นจะคืนค่า -1 อาร์เรย์สามารถเก็บตัวเลขติดลบได้เช่นกัน และองค์ประกอบข้อมูลจะถูกจัดเรียง
เราจะใช้วิธีการค้นหาแบบไบนารีเพื่อแก้ปัญหานี้ในเวลา O(log n) ขั้นแรกเราจะตรวจสอบว่าองค์ประกอบตรงกลางเป็นจุดคงที่หรือไม่ ถ้าใช่ ก็ให้คืน ถ้าไม่เช่นนั้นจะมีสองกรณี ถ้าดัชนีขององค์ประกอบกลางมากกว่าค่าที่ดัชนี ถ้าดัชนีมากกว่า แล้วมีโอกาสได้จุดคงที่ทางด้านขวามือ มิฉะนั้น จะอยู่ที่ด้านซ้ายมือ
ตัวอย่าง
#include<iostream>
using namespace std;
int getFixedPoint(int arr[], int left, int right) {
if(right >= left){
int mid = (left + right)/2; /*low + (high - low)/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);
} ผลลัพธ์
Fixed Point: 3
