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

Ở đây chúng ta sẽ xem cách tìm điểm cố định trong một mảng nhất định. Trong mảng, một phần tử sẽ được biểu thị là điểm cố định nếu giá trị giống với chỉ số của nó. Chương trình này sẽ trả về giá trị nếu có, nếu không thì trả về -1. Mảng này cũng có thể chứa các số âm. Và các phần tử dữ liệu được sắp xếp.

Ở đây chúng ta sẽ sử dụng phương pháp tìm kiếm nhị phân để giải quyết vấn đề này trong thời gian O (log n). Đầu tiên chúng ta sẽ kiểm tra xem phần tử ở giữa có phải là điểm cố định hay không, nếu có thì trả về, nếu không thì sẽ xảy ra hai trường hợp, nếu chỉ số của phần tử giữa lớn hơn giá trị tại chỉ mục, nếu chỉ số lớn hơn , thì sẽ có cơ hội lấy được điểm cố định ở bên tay phải, nếu không thì ở bên tay trái.

Ví dụ

#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);
}

Đầu ra

Fixed Point: 3