Find Equal (or Middle) Point in a sorted array with duplicates - GeeksforGeeks

Find Equal (or Middle) Point in a sorted array with duplicates - GeeksforGeeks
Given a sorted array of n size, the task is to find whether an element exists in the array from where number of smaller elements is equal to number of greater elements.
If Equal Point appears multiple times in input array, return index of its first occurrence. If doesn't exist, return -1.

A Naive approach is take every element and count how many elements are smaller than that and then greater element. Then compare if both are equal or not.

An Efficient approach is to create an auxiliary array and store all distinct elements in it. If count of distinct elements is even, then Equal Point does not exist. If count is even, then equal point is middle point of the auxiliary array.

int findEqualPoint(int arr[], int n)

{

     // To store first indexes of distinct elements of arr[]

     int distArr[n];

 

     // Travers input array and store indexes of first

     // occurrences of distinct elements in distArr[]

     int i = 0, di = 0;

     while (i < n)

     {

        // This element must be first occurrence of a

        // number (this is made sure by below loop),

        // so add it to distinct array.

        distArr[di++] = i++;

 

        // Avoid all copies of arr[i] and move to next

        // distinct element.

        while (i<n && arr[i] == arr[i-1])

             i++;

     }

 

     // di now has total number of distinct elements.

     // If di is odd, then equal point exists and is at

     // di/2, otherwise return -1.

     return (di & 1)? distArr[di>>1] : -1;

}

Time Complexity : O(n)
Auxiliary Space : O(n)

Space Optimization : 
We can reduce extra space by traversing the array twice instead of once.

1. Count total distinct elements by doing a traversal of input array. Let this count be distCount.
2. If distCount is even, return -1.
3. If distCount is odd, traverse the array again and stop at distCount/2 and return this index.

Time Complexity : O(n)
Auxiliary Space : O(n)

Space Optimization : 
We can reduce extra space by traversing the array twice instead of once.

1. Count total distinct elements by doing a traversal of input array. Let this count be distCount.
2. If distCount is even, return -1.
3. If distCount is odd, traverse the array again and stop at distCount/2 and return this index.

Read full article from Find Equal (or Middle) Point in a sorted array with duplicates - GeeksforGeeks