Giả sử chúng ta có một mảng đã sắp xếp với n phần tử. Mảng được sắp xếp. Chúng ta phải tìm xem một phần tử có tồn tại trong một mảng mà từ đó số phần tử nhỏ hơn bằng số phần tử lớn hơn hay không. Nếu điểm bằng nhau xuất hiện nhiều lần trong mảng, hãy trả về chỉ số của lần xuất hiện đầu tiên. Nếu không có điểm nào như vậy thì trả về -1. Giả sử các phần tử giống như A =[1, 1, 2, 3, 3, 3, 3, 3] thì điểm bằng nhau nằm ở chỉ số 2, phần tử là A [2] =2. Vì nó chỉ có một nhỏ hơn phần tử là 1 và chỉ một phần tử lớn hơn, đó là 3.
Chúng tôi sẽ tạo một mảng bổ trợ để lưu trữ tất cả các phần tử riêng biệt trong đó. Nếu số lượng các phần tử riêng biệt là chẵn thì chúng ta không thể tìm thấy bất kỳ điểm nào bằng nhau, nếu không phần tử ở giữa sẽ là điểm giữa.
Ví dụ
#include<iostream>
using namespace std;
int searchEqualPoint(int arr[], int n) {
int aux_arr[n];
int i = 0, aux_index = 0;
while (i < n) {
aux_arr[aux_index++] = i++;
while (i<n && arr[i] == arr[i-1])
i++;
}
return (aux_index & 1)? aux_arr[aux_index>>1] : -1;
}
int main() {
int arr[] = {1, 1, 2, 3, 3, 3, 3, 3};
int n = sizeof(arr)/sizeof(arr[0]);
int index = searchEqualPoint(arr, n);
if (index != -1)
cout << "Equal Point is: " << arr[index];
else
cout << "No Equal Point exists";
} Đầu ra
Equal Point is: 2