สมมติว่าเรามีอาร์เรย์ที่เรียงลำดับหนึ่งรายการที่มีองค์ประกอบ n อาร์เรย์ถูกจัดเรียง เราต้องค้นหาว่าองค์ประกอบนั้นมีอยู่ในอาร์เรย์หรือไม่ โดยที่จำนวนองค์ประกอบที่เล็กกว่านั้นเท่ากับจำนวนองค์ประกอบที่ใหญ่กว่า หากจุดเท่ากันปรากฏขึ้นหลายครั้งในอาร์เรย์ ให้คืนค่าดัชนีของการเกิดครั้งแรก หากไม่มีจุดดังกล่าว ให้ส่งกลับ -1 สมมติว่าองค์ประกอบมีลักษณะเหมือน A =[1, 1, 2, 3, 3, 3, 3, 3] จากนั้นจุดเท่ากันอยู่ที่ดัชนี 2 องค์ประกอบคือ A[2] =2 เนื่องจากมีขนาดเล็กกว่าเพียงตัวเดียว องค์ประกอบที่เป็น 1 และองค์ประกอบที่ใหญ่กว่าเพียงตัวเดียวนั่นคือ 3
เราจะสร้างอาร์เรย์เสริมหนึ่งชุดเพื่อเก็บองค์ประกอบที่แตกต่างกันทั้งหมดไว้ หากการนับองค์ประกอบที่แตกต่างกันเป็นจำนวนเท่ากัน เราจะไม่พบจุดเท่ากัน มิฉะนั้น องค์ประกอบตรงกลางจะเป็นจุดกึ่งกลาง
ตัวอย่าง
#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";
} ผลลัพธ์
Equal Point is: 2
