Finding an element in an array nd change the size of an array

Finding an element in an array

There are many ways find the location of a value in an array. The following example snippets all assume that the array is one of the following:

 String[] strings = new String[] { "A", "B", "C" };
 int[] ints = new int[] { 1, 2, 3, 4 };

In addition, each one sets index or index2 to either the index of required element, or -1 if the element is not present.

Using Arrays.binarySearch (for sorted arrays only)

 int index = Arrays.binarySearch(strings, "A");
 int index2 = Arrays.binarySearch(ints, 1);

Using a Arrays.asList (for non-primitive arrays only)

int index = Arrays.asList(strings).indexOf("A");
int index2 = Arrays.asList(ints).indexOf(1); // compilation error

Using a Stream

int index = IntStream.range(0, strings.length)
                 .filter(i -> "A".equals(strings[i]))
                 .findFirst()
                 .orElse(-1); // If not present, gives us -1.
 // Similar for an array of primitives

Linear search using a loop

int index = -1;
for (int i = 0; i < array.length; i++) {
    if ("A".equals(array[i])) {
         index = i;
         break;
    } 
}
// Similar for an array of primitives

Linear search using 3rd-party libraries such as org.apache.commons

int index = org.apache.commons.lang3.ArrayUtils.contains(strings, "A");
int index2 = org.apache.commons.lang3.ArrayUtils.contains(ints, 1);
 

Note : Using a direct linear search is more efficient than wrapping in a list

Testing if an array contains an element

The examples above can be adapted to test if the array contains an element by simply testing to see if the index computed is greater or equal to zero.

Alternatively, there are also some more concise variations:

boolean isPresent = Arrays.asList(strings).contains("A");
 
boolean isPresent = Stream<String>.of(strings).anyMatch(x -> "A".equals(x));
boolean isPresent = false;
for (String s : strings) {
  if ("A".equals(s)) {
     isPresent = true;
     break;
  }
}
 
boolean isPresent = org.apache.commons.lang3.ArrayUtils.contains(ints, 4);

How do you change the size of an array?

The simple answer is that you cannot do this. Once an array has been created, its size cannot be changed. Instead, an array can only be "resized" by creating a new array with the appropriate size and copying the elements from the existing array to the new one.

String[] places = new String[4]; // Array initialized with a size of 4.
places[0] = "Paris";
places[1] = "Tokyo";
places[2] = "Sydney";
places[3] = "Rome";

Suppose (for example) that a new element needs to be added to the listOfCities array defined as above. To do this, you will need to:

  • create a new array with size 4,
  • copy the existing 3 elements of the old array to the new array at offsets 0, 1 and 2,and 3, and
  • add the new element to the new array at offset 4

There are various ways to do the above. Prior to Java 6, the most concise way was:

String[] updatedArray = new String[places.length + 1];
System.arraycopy(places, 0, updatedArray, 0, places.length);
updatedArray[places.length] = "Berlin";

From Java 6 onwards, the Arrays.copyOf and Arrays.copyOfRange methods can do this more simply:

String[] updatedArray = Arrays.copyOf(citiesArray, citiesArray.length + 1);
updatedArray[citiesArray.length] = "Tokyo";

For other ways to copy an array, refer to the following example. Bear in mind that you need an array copy with a different length to the original when resizing.

  • Copying arrays

A better alternatives to array resizing

There two major drawbacks with resizing an array as described above:

  • It is inefficient. Making an array bigger (or smaller) involves copying many or all of the existing array elements, and allocating a new array object. The larger the array, the more expensive it gets.
  • You need to be able to update any "live" variables that contain references to the old array.

One alternative is to create the array with a large enough size to start with. This is only viable if you can determine that size accurately before allocating the array. If you cannot do that, then the problem of resizing the array arises again.

The other alternative is to use a data structure class provided by the Java SE class library or a third-party library. For example, the Java SE "collections" framework provides a number of implementations of the List, Set and Map APIs with different runtime properties. The ArrayList class is closest to performance characteristics of a plain array (e.g. O(N) lookup, O(1) get and set, O(N) random insertion and deletion) while providing more efficient resizing without the reference update problem.

(The resize efficiency for ArrayList comes from its strategy of doubling the size of the backing array on each resize. For a typical use-case, this means that you only resize occasionally. When you amortize over the lifetime of the list, the resize cost per insert is O(1). It may be possible to use the same strategy when resizing a plain array.)

Basic Programs

Learn All in Tamil © Designed & Developed By Tutor Joes | Privacy Policy | Terms & Conditions