Bits of Java – Episode 11: Compare and Search in Arrays

This week I would like to talk about two methods of the Arrays class which I was not familiar with, and whose logic can be a bit tricky: Arrays.binarySearch and Arrays.compare.

But first, let me briefly review what an array is. An array is a memory section which is reserved on the heap at declaration time for a designated number of elements, depending on the array size. We can have an array of any Java type. Keep in mind, that an array can contain duplicates.

That said, the Arrays class is defined in the java.util package, so if you want to use the methods we are going to describe, remember to import that package.

Now we are all set, so let’s start!

• Arrays.binarySearch: this is a useful method to search within an array, as the name suggests. The first important thing to remember about this method is that it works only if the array is already sorted. If this is not the case, the result of calling this method is completely unpredictable.

  For sorting an array you can use another method provided by the same class, Arrays.sort. The sorting rules are:

  • String are sorted in alphabetical order, upper cases come before lower cases and numbers come before letters, with “1” being before “9”;
  • numbers are sorted in natural order.

  So, coming back to our binarySearch. Once you are sure your array is sorted, you can call this method. It takes two parameters: the first one is the array you want to search in, and the second is the element you want to search for.

  If such element is found, the method returns the index of its first occurrence, otherwise, and here comes the tricky part, it returns an int value which is equal to the negative of the index in which that element should be inserted maintaining the order, minus 1 unit. Let’s see an example to better understand the logic:

    
  int[] oddNumbers = {1,3,5,7,9};
    
  /*
  * The element 1 exists and its first occurrence is at index 0,
  * so it prints 0
  */
  System.out.println(Arrays.binarySearch(oddNumbers, 1));
    
  /*
  * The element 2 is not present. The index where it should be put
  * to mantain the order is the index 1. Its negative is -1 and minus
  * one unit gets -2, so it prints -2
  */
  System.out.println(Arrays.binarySearch(oddNumbers, 2));
    
  /*
  * The element 3 exists and its first occurrence is at index 1,
  * so it prints 1
  */
  System.out.println(Arrays.binarySearch(oddNumbers, 3));
    
  /*
  * The element 4 is not present. The index where it should be put
  * to mantain the order is the index 2. Its negative is -2 and minus
  * one unit gets -3, so it prints -3
  */
  System.out.println(Arrays.binarySearch(oddNumbers, 4));
    
  /*
  * The element 10 is not present. The index where it should be put
  * to mantain the order is the index 5. Its negative is -5 and minus
  * one unit gets -6, so it prints -6
  */
  System.out.println(Arrays.binarySearch(oddNumbers, 10));
    
  

Remember that this worked because we use an array which was already sorted, otherwise results are unpredictable!

• Arrays.compare: this method is useful when we want to compare two arrays, so it takes as parameters the two arrays we want to compare. The content of the two arrays is compared to see whether one is smaller than the other.

  But what does smaller mean in this context? We can immediately say that it is not a smaller in the sense of the size of the arrays (indeed for that we could just check the length of the arrays). The rules apply in determining whether an array is smaller than the other:

  • null is smaller than any other value;
  • for numerical arrays, the normal numeric order applies (as for sorting);
  • for String arrays, if a String is a prefix of another, then it is considered smaller; otherwise the same rules as for sorting apply, and if a String would be sorted before another, it is considered smaller.

  Now that we know what smaller means, we can look at the returning values of the compare method:

  • If both the arrays are of the same length and they have the same values in the same order, it returns 0;
  • If the first element which is different is smaller in the first array, then returns a negative number;
  • If the first element which is different is larger in the first array, then returns a positive number;
  • If the length of the arrays is different, the values are the same in the same order, but the second array has extra elements at the end, then return a negative number;
  • If the length of the arrays is different, the values are the same in the same order, but the first array has extra elements at the end, then return a positive number.

  Let’s look at some examples.

  int[] numbers = {3,6,2,98,43};
  int[] otherNumbers = {3,100,36,2,33};

  /*
  * The two arrays have the same length. The first element which is different
  * is the second one and, since they are numbers, the one in the second array is
  * larger, so the method will return a negative number
  */
  System.out.println(Arrays.compare(numbers, otherNumbers));

  String[] words = {"3","6","2","98","43"};
  String[] otherWords = {"3","100","36","2","33"};

  /*
  * The two arrays have the same length. The first element which is different
  * is the second one and, but now they are String, so "1" comes before "6" in
  * sorting, making the element of the second array smaller than the one in the
  * first array. So, this will print a positive number
  */
  System.out.println(Arrays.compare(words, otherWords));

  int[] againNumbers = {3,6,2,98,43};
  int[] againOtherNumbers = {3,6,2,98,43,5};

  /*
  * The two arrays have NOT the same length. All the elements are the same and
  * in the same order, but the second array has one extra element at the end,
  * so the comparison will return a negative number
  */
  System.out.println(Arrays.compare(numbers, otherNumbers));

To conclude, we have looked at two useful methods when dealing with arrays. We just need to pay attention at the different rules for sorting and how the concept of an array being smaller than another is defined, in order to be able to correctly interpret the results!

Next week we will talk about the wrapper classes for primitive types!

by Ilenia Salvadori