Tìm một điểm cố định trong một mảng có phép trùng lặp 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 cho phép các phần tử trùng lặp trong mảng.

Ở đâ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). Nhưng chúng tôi cần một số sửa đổi, nếu tìm kiếm nhị phân thông thường được sử dụng, thì nó có thể không thành công đối với các phần tử trùng lặp. Để kiểm tra bên trái, chúng ta phải bắt đầu từ min (mid - 1, midValue) và để kiểm tra bên phải, chúng ta phải bắt đầu đến max (mid + 1, midValue).

Ví dụ

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

Đầu ra

Fixed Point: 2