Arrays class, part 2

"Rishi, I'm really looking forward to learning about the rest of the methods of the Arrays class.

"Such zeal for learning cannot but please your old teacher! But, if you really want to find out everything, a kind wizard named Google will help you day and night."

"Uh..."

"Just kidding. Kind of. Of course, I'll explain everything better, but if something comes up anything - remember the good wizard. I'll start today's lesson with the Arrays.fill method

"When working with arrays, Java programmers very often need to fill the array with the same value. You can, of course, write a loop and simply assign some value to each cell of the array in the loop:

int[] x = new int[100];
for (int i = 0; i < x.length; i++)
x[i] = 999;

"Or instead of all this, you can call the Arrays.fill() method, which does exactly the same thing: it fills the passed array with the passed value. Here's how it looks:

Arrays.fill(name, value)

And the code in the example above can be made a little bit more compact and clearer:

int[] x = new int[100];
Arrays.fill(x, 999);

"Beautiful!"

"You can also use the Arrays.fill() method to fill not the entire array, but a part of it, with some value:

Arrays.fill(name, first, last, value)

"Where first and last are the indices of the first and last cells to be filled.

"In accordance with Java's good (or bad) old tradition, remember that the last element is not included in the range.

Example:

int[] x = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

Arrays.fill(x, 3, 7, 999);


String str = Arrays.toString(x);

"The Arrays.fill() method only works with one-dimensional arrays. If you pass a two-dimensional array to the method, it will be treated as one-dimensional, with all the ensuing consequences.

Arrays.copyOf()

"Amigo, please tell me how to change the size of an array after it has been created?"

"Umm... That's a trick question, right? I'm not that inexperienced anymore. The correct answer is that you can't! You cannot resize an array after it has been created."

"But what if you really want to?"

"It's still impossible!

"Actually, if you really want to, then you can! With the help of a programming trick:

1. First, you create a new array of the desired length
2. Then you copy all the elements from the first array into it.

"These are the two things that the Arrays.copyOf() method does. This is what calling it looks like:

Type[] name2 = Arrays.copyOf(name, length);

"This method does not change the existing array, but instead creates a new array and copies the elements of the old array into it."

"What if the length of the new array is less than the length of the existing one?

"Great question, Amigo! If the elements don't fit, then the extra values are simply ignored."

"And if, on the contrary, there are extra cells, what are their initial values?

"If the length of the new array is greater than the length of the old one, the cells are filled with zeros.

Example:

int[] x = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

int[] x2 = Arrays.copyOf(x, 5);
String str2 = Arrays.toString(x2);

int[] x3 = Arrays.copyOf(x, 15);
String str3 = Arrays.toString(x3);

Arrays.copyOfRange()

"And what if you want to get an array of length 5 from an array of length 10, but you need it to contain the last 5 elements rather than the first 5? In this case, you need another method of the Arrays class. It is Arrays.copyOfRange(). This is what calling it looks like:

Type[] name2 = Arrays.copyOfRange(name, first, last);

"This method also creates a new array, but fills it with elements from an arbitrary place in the original array. Where first and last are the indices of the first and last elements that should be put into the new array. Can you tell me whether the last element is included in this range?"

"Ha! As my great teacher used to say, 'in accordance with Java's good (or bad) old tradition, remember that the last element is not included in the range'."

"Amigo, you are growing right before our eyes.

Example:

int[] x = {11, 12, 13, 14, 15, 16, 17, 18, 19, 20};

int[] x2 = Arrays.copyOfRange(x, 5, 10);
String str2 = Arrays.toString(x2);

int[] x3 = Arrays.copyOfRange(x, 5, 15);
String str3 = Arrays.toString(x3);

Arrays.sort()

"And finally, I left the most... mmm... pleasant method for last: sorting. Arrays are sorted quite often in programming. Here are the top 3 most popular actions when working with arrays:

• Sorting an array
• Finding the minimum (or maximum) element of an array
• Determining the index of an element in an array (finding an element in an array)

"Well-performing sorting algorithms, I must say, are not so easy to write. More precisely, this is a standard task, and as a student, it won't hurt you to practice writing sorting algorithms sometimes. But at work, it's better not to waste your time reinventing the wheel. Java's creators included the sort() method in the Arrays class. This is what calling it looks like:

Arrays.sort(name);

This method sorts the passed array in ascending order.

Example:

int[] x = {11, -2, 3, 0, 999, -20, 8, -20, 99, -20};

Arrays.sort(x);
String str = Arrays.toString(x);

"Excellent! I called just one method and the array is sorted. A thing of beauty!"

"By the way, you can sort not only the entire array, but also just part of it. This is what calling it looks like:

Arrays.sort(name, first, last);

"Where first and last are the indices of the first and last cells that the sort should touch. AND…

"I already know what you're going to say! 'In accordance with Java's good (or bad) old tradition, remember that the last element is not included in the range'.

Example:

int[] x = {11, -2, 3, 0, 999, -20, 8, -20, 99, -20};

Arrays.sort(x, 4, 8);
String str = Arrays.toString(x);

"To sort arrays, Java uses the fastest sorting algorithm — QuickSort. Its computational complexity depends on the size of the array and is calculated using the formula N log(N).

"Sorting an array of 1000 elements will involve about 10,000 comparisons of array elements. Sorting an array of one million elements will involve about 20 million comparisons."

"Not too many comparisons when you consider the number of elements!"

"That's exactly what I'm saying. The QuickSort algorithm is very efficient.

Arrays.binarySearch()

"Well, and the last of the most interesting methods of the Arrays class is able to search for a given value in an array. This is no ordinary search — it is the beloved binary search. It boils down to this:

• First, the array is sorted.
• Then the middle element of the array is compared with the one we are looking for.
• If the element is greater than the middle element, then the search continues in the right half of the array.
• If the element we are looking for is less than the middle element, then the search continues in the left half of the array.

"Because the array is sorted, it is possible to eliminate half of it in a single comparison. Then in the next step, we toss out another half, and so on."

"Fantastic! We move straight to the goal very quickly!"

"Exactly. In an array of one million (!) elements, the binary search algorithm can find the index of the desired element in just 20 comparisons. The algorithm's shortcoming is that the array must first be sorted, and sorting also takes time.

This is what calling it looks like:

int index = Arrays.binarySearch(name, value);

"Where name is the name of the array, which must be passed already sorted (for example, using the Arrays.sort() method). And value is the element we are searching for in the array. The result returned by the method is the index of the desired array element.

Examples:

int[] x = {11, -2, 3, 0, 999, -20, 8, -20, 99, -20};
Arrays.sort(x);

int index1 = Arrays.binarySearch(x, 0);
int index2 = Arrays.binarySearch(x, -20);
int index3 = Arrays.binarySearch(x, 99);
int index4 = Arrays.binarySearch(x, 5);

"What if the desired element appears multiple times in the array?"

"That's a valid question, Amigo. In this case, the algorithm will return the index of one of them (there is no guarantee that it will be, say, the very first, or vice versa — the very last of these duplicate elements)."

"What if the array doesn't contain the desired element at all?"

"In this case, the algorithm will return a negative index.

Documentation

"Everything is clear, Rishi! This was very interesting."

"If you truly found this very interesting, then at your leisure skim through the official documentation of the Arrays class and its methods on the Oracle website.

"You can take a closer look at, for example, the Arrays.mismatch() and Arrays.compare() methods. You will most likely be able to put them to good use.

"And don't be confused by the number of methods. Each method has 5-10 variants, which differ only in their parameter types."