1. Introduction
In this tutorial, we’ll explore the problem of finding an array’s middle element(s). An array is a data structure that stores data elements of the same type.
The elements of the array are stored in a contiguous fashion in memory and are associated with an index. The array has a fixed length.
2. Problem Statement
Given an array of n elements, we are supposed to return a new array containing the array’s middle element(s). In case the input array is of odd length, there is one middle element for the array. On the other hand, if the input array is of even length, there are two middle elements of the array.
The output of our code should return an array of either length 1 or 2, depending on the input array.
Let’s see some examples:
- Given an input array of 5 elements: [1, 2, 3, 4, 5], the output is [3]. As the array’s length is 5, which is an odd number, we can say that a single middle element exists, in our case 3.
- Given an input array of 6 elements: [1, 2, 3, 4, 5, 6], the output is [3, 4]. The array’s length in this case is 6, which is even. Here, both 3 and 4 are the middle elements of the array.
We should also consider a few edge cases for our problem. For an empty input array, there is no middle element, and hence an empty array is the correct output. The array itself is the output for arrays of lengths 1 and 2.
3. Middle Element(s) Using Array Operations
An array’s length tells us the number of elements it contains. An array of length n will contain n number of elements in it. The elements can be accessed with a 0-based index.
3.1. Middle Element of Arrays of Odd Length
Given an array of length n, where n is an odd number, we can say that the array’s first index is always 0, and the last index of the array is n-1. An array of length 99 has indices running from 0 through 98, with index 49 being the middle index.
We know that the middle point between two values, a and b, is always (a + b) / 2. In our case, considering a = 0 and b = n = 98, we can find the middle index to be (0 + 99) / 2 = 49. Hence, accessing the n/2 element will give us our desired output:
int[] middleOfArray(int[] array) {
int n = array.length;
int mid = n / 2;
return new int[] { array[mid] };
}
It is important to note that n is always an integer as it tells us about the array’s length, and length cannot be fractional. Hence, when we perform n/2, Java will perform an Integer division and will discard the decimal part. So, in our previous example of 99 elements, the middle element will be 99/2 = 49 and not 49.5 or 50.
3.2. Middle Elements of Arrays of Even Length
Now that we know how to find the middle element of an odd-length array, let’s extend the solution to arrays of even length.
There is no defined single middle element of an array of even length. An array of length 100 with elements starting from index 0 will have its middle elements at index 49 and 50. Hence, the middle elements of an array of length n, where n is even, are the elements at index (n/2)-1 and n/2. As our output depends on the length of the input array, let’s combine them into a single method:
int[] middleOfArray(int[] array) {
if (ObjectUtils.isEmpty(array) || array.length < 3) {
return array;<br /> }
int n = array.length;
int mid = n / 2;
if (n % 2 == 0) {
int mid2 = mid - 1;
return new int[] { array[mid2], array[mid] };
} else {
return new int[] { array[mid] };
}
}
Let’s also add a small test to verify that our solution works for all types of arrays:
int[] array = new int[100];
for (int i = 0; i < array.length; i++) {
array[i] = i + 1;
}
int[] expectedMidArray = { 50, 51 };
MiddleOfArray middleOfArray = new MiddleOfArray();
Assert.assertArrayEquals(expectedMidArray, middleOfArray.middleOfArray(array));
int[] expectedMidArrayForOddLength = { 50 };
Assert.assertArrayEquals(expectedMidArrayForOddLength, middleOfArray.middleOfArray(Arrays.copyOfRange(array, 0, 99)));
3.3. Middle Element of an Array Between Two Points
In our previous sections, we considered the entire length of the array to be our input, and we calculated the middle of the entire array. A need to calculate the middle element(s) of a portion of the array or a subset given by a start and an end index might arise.
We cannot use the value of n, the length of the array to calculate the middle point anymore. Instead of substituting start = 0 and end = n as we did before, we can use the provided values as is and find the middle point: middle = (start + end) / 2.
int[] middleOfArrayWithStartEnd(int[] array, int start, int end) {
int mid = (start + end) / 2;
int n = end - start;
if (n % 2 == 0) {
int mid2 = mid - 1;
return new int[] { array[mid2], array[mid] };
} else {
return new int[] { array[mid] };
}
}
However, this approach has a major drawback.
Consider that we are dealing with an array with a very large size in the order of Integer.MAX_VALUE. The value Integer.MAX_VALUE is 2147483647. We are required to find the middle element of the array between indices 100 and 2147483647*.*
So in our example, start = 100 and end = Integer.MAX_VALUE. When we apply the formula to find the midpoint, start + end is 4294966747. This value is greater than the Integer.MAX_VALUE and thereby leads to overflow. When we run this in Java, we get -2147483549, which confirms the overflow.
The fix for this is rather simple. We start by finding the difference between the two values, start and end, and then add (end – start) / 2 to start. So, mid = start + (end – start) / 2. This always saves us from overflow:
int[] middleOfArrayWithStartEnd(int[] array, int start, int end) {
int mid = start + (end - start) / 2;
int n = end - start;
if (n % 2 == 0) {
int mid2 = mid - 1;
return new int[] { array[mid2], array[mid] };
} else {
return new int[] { array[mid] };
}
}
3.4. Performance of Array Operations to Find the Middle Elements
We know that accessing an element in an array is an O(1) operation. As array elements are placed in contiguous blocks in memory, jumping to a specific index is a constant time operation. Hence, we can say that all the above operations are constant time O(1) operations.
4. Middle Element(s) Using Bitwise Operations
We can use Bitwise operations as an alternative to find the middle elements of an array. Bitwise operations are operations which work on binary digits(bits) of input values. There are many categories of bitwise operators such as Bitwise Logical Operators and Bitwise Shift Operators.
Here we’ll use a specific type of shift operator called the unsigned right shift operator, i.e. >>>.
An unsigned right shift operator, as the name suggests shifts all the bits of the input value to the right and the newly created empty spaces are filled with 0. This helps in asserting that the output will always be positive.
Unsigned shift operators are popularly used to divide a number by a power of 2. So, a >>> n is equivalent to a / (2 ^ n). We use this fact to find the middle element(s) between start and end:
int[] middleOfArrayWithStartEndBitwise(int[] array, int start, int end) {
int mid = (start + end) >>> 1;
int n = end - start;
if (n % 2 == 0) {
int mid2 = mid - 1;
return new int[] { array[mid2], array[mid] };
} else {
return new int[] { array[mid] };
}
}
Bitwise operations such as these are faster as they are implemented at a lower level in the hardware, and modern CPUs can take advantage of it.
5. Median of an Array
In our discussions, we didn’t talk about the nature of elements or their order. A special case arises if the elements in the array are all numerical and sorted in nature.
The middle element of a sorted data set is called the median value of the dataset and is of great importance in mathematics and statistics. The Median value is a measure of the central tendency of any data set and provides insights into what the typical value of the dataset could be.
For an array of even length, the median is typically computed by finding the average of the two middle elements:
int medianOfArray(int[] array, int start, int end) {
Arrays.sort(array); // for safety. This can be ignored
int mid = (start + end) >>> 1;
int n = end - start;
if (n % 2 == 0) {
int mid2 = mid - 1;
return (array[mid2] + array[mid]) / 2;
} else {
return array[mid];
}
}
The median value expects the data set to be in sorted order to be correct. So if we are unsure of the array’s nature, we should first sort the array in ascending or descending order and then find the middle value using any of the previous methods.
Consider a problem statement where we are required to find the median house price of a country. Given the nature of the problem, we can assume that the input data will be too large to fit in the available memory of a conventional computer. If the JVM is not able to load the entire array in memory at a time, it would be difficult to apply the methods mentioned above to find the median.
In such cases where the data set is too large to fit in memory, we can consider the input to be in a stream rather than a conventional array. We can then find the median of the data stream using additional data structures, such as a Heap with streaming data.
6. Conclusion
In this article, we looked at several approaches to finding the middle elements of an array. We also talked about how this solution can help us find the median of an array.
As usual, all code samples can be found over on GitHub.