Algorithms and Data Structures in an Object-Oriented Framework (“ADSOOF”)

Finding the biggest

Biggest integer in an array of integers

A common operation on an array of integers might be not to find whether a specific integer is present, but to find which is the biggest integer. For example, with the array:

the biggest integer is 119. A variation on this would be to return not the biggest integer itself, but the position of the biggest integer, which in this case would be 7 (remembering that in Java we always start counting positions at 0).

We need to think of a way of doing this - or to use the formal term, an “algorithm”. It is important that our algorithm doesn't make any changes to the array, because any such change would carry on after the method to find the biggest integer has finished. It could cause a serious error if we called a method to find the biggest integer in an array, and unknown to us that method also moved integers around in the array. A method must always do just what it is intended to do, it must never have any unexpected side-effects caused by changing things around in arrays and other objects passed to it as arguments. Of course, if we want a method to change things around, that's fine, but then we should clearly specify that. So once again, we have the importance of specification - always make sure before you write a method that you have clearly specified what it is intended to do, then when you write it make sure it does that and nothing else.

I have sometimes seen the following algorithm used to find the biggest item in an array: “swap the first item with the second if it is bigger than it, then swap the second item with the third if it is bigger, then carry on comparing adjacent items and swapping until you reach the end - the biggest item then will have 'bubbled up' to the end, and you can return it“. I think the reason this is given is that it is a sub-operation of the bubble sort algorithm, which is often given as an example in introductory programming teaching, so people remember it from that. It does find the biggest item, but also moves things around in the array. Because it moves things around in the array, it's just not acceptable as the solution if all you want is to find and return the biggest item.

The most obvious algorithm is as follows. Have a variable to hold the biggest item so far. Set it initially to the first item. Then go through each of the remaining items in turn, if you find one which is bigger than the biggest item so far, replace the value of the biggest item so far by that new value. When you have gone through all the items, the variable holding the biggest item so far must hold the biggest item of all the items. We go through items in turn using the technique we are familiar with of an index variable increased by 1 each time round a loop. If the array of integers is referred to by the variable a, the following code fragment will do this:

int biggestSoFar=a[0];
for(int i=1; i<a.length; i++)
   if(a[i]>biggestSoFar)
      biggestSoFar=a[i]

As previously, we can put our code fragment to do a job inside a method:

static int biggest(int[] a)
{
 int biggestSoFar=a[0];
 for(int i=1; i<a.length; i++)
    {
     if(a[i]>biggestSoFar)
        biggestSoFar=a[i];
    }
 return biggestSoFar;
}

A variation on the theme is a method which instead of returning the biggest integer in an array of integers return the position of the biggest integer in an array of integers. Here's the code for it:

static int posBiggest(int[] a)
{
 int posBiggestSoFar=0;
 for(int i=1; i<a.length; i++)
    {
     if(a[i]>a[posBiggestSoFar])
        posBiggestSoFar=i;
    }
 return posBiggestSoFar;
}

In the code index there is a link to the file UseArrays14.java which gives a method for finding the largest integer in an array of integers, and a front end for running it. The file UseArrays15.java gives the method for finding the position of the largest integer in an array of integers, and a front end for running it.

Special cases

When writing code, we must always make sure we have considered all possible cases, not just the obvious ones. The code we have given assumes the array passed as an argument has at least one item in it. It is possible for an array to have 0 length. In this case, when biggestSoFar=a[0] is executed, we will get an ArrayIndexOutOfBoundsException thrown. If that's acceptable, it should still be noted that it's what happens when the argument is a 0-length array. If we wanted instead to return some special value, we should make sure it's a value which could never be returned in other circumstances. When returning the position of the biggest integer, a special value of -1 is fine, as -1 could never be a real position. But it isn't fine for the biggest integer in an array, as we could have an array of integers which happens to hold only negative integers, in which case -1 could be the biggest integer in it. Note here we're being sloppy about what we meant by “biggest”. We actually mean “greatest in numerical order”. Informally many people would think that -100 is “bigger” than -1. If the integers are sums of money, -100 is a debt of a hundred pounds, and that's “bigger” than a debt of one pound. So we really needed to specify more clearly what we meant by “bigger”.

It's also possible for an array variable to be set to null, which as mentioned previously is not the same thing as as array of length 0. Again, this would be discovered when biggestSoFar=a[0] is executed, but this time a NullPointerException would be thrown. This is likely to be acceptable, but again we should note it if we want to make sure we have fully specified our method.

The other thing to consider is what if the biggest integer in the array occurs more than once. Suppose in the array we used as an example above, instead of 119 we had 19. In that case, the biggest integer in the array is 54, and 54 occurs in position 1 and position 6. That's no problem when returning the biggest integer, with our code in this case when i is 6, the test a[i]>biggestSoFar will evaluate to false as a[i] and biggestSoFar will both be equal to 54, and 54 is returned in the end. It is unlikely we would want anything else done to indicate that the value returned is the biggest but occurs more than once, but to be on the safe side we should note that's how it works.

When we come to the position of the biggest integer, however, it's more tricky. Should we return 6 or 1 or do something special to indicate there isn't a unique biggest integer? When we have an unclear specification, the best thing is to ask for clarification. We should not take it on ourselves to make it do some special action that we were never asked for. For example, don't return -2 as a special code to mean “the biggest integer occurred twice” unless that was actually given to you as what to do. The best thing to do here would be to leave the code as it is, and just note that means when the biggest integer occurs more than once it will return the position of its lowest indexed occurrence. Of course, if you wanted the position of its highest indexed occurrence when it occurred more than once, you could just reverse the order you go through the array:

static int posBiggest(int[] a)
{
 int posBiggestSoFar=a[a.length-1];
 for(int i=a.length-2; i>=0; i--)
    {
     if(a[i]>a[posBiggestSoFar])
        posBiggestSoFar=i;
    }
 return posBiggestSoFar;
}

An incorrect algorithm

I have often seen code something like the following given by students as a solution to a “finding the biggest” problem:

static int biggest(int[] a)
// THIS IS SILLY CODE!
{
 int biggestSoFar=a[0];
 for(int i=0; i<a.length-1; i++)
    {
     if(a[i]>a[i+1])
        biggestSoFar=a[i];
     else
        biggestSoFar=a[i+1];
    }
 return biggestSoFar;
}

However, a little bit of thought about this code should indicate why it will not work correctly. On each time round the loop it sets to variable biggestSoFar either to a[i] or to a[i+1]. So, unlike the correct algorithm, each time round the loop no use is made of the previous value of biggestSoFar. This means that on the last time round the loop it will set biggestSoFar either to the last item in the array or the next-to-last. So, it will only ever return whichever is the biggest of the last two items. For the array given above it would return 23 rather than 119, because 23 is the biggest out of 7 and 23.

The fact that in tests and exams students often come up with code like this where it ought to be obvious that it is wrong illustrates the important point that trying to memorise and recall code is just not the way to learn to program. When you write code, you must always think carefully through about what it is actually doing. You should be able to think about it in terms of its algorithm, rather than just its visual resemblance to what you think is the required solution.

Generalising

What if we wanted the smallest rather than the biggest integer in an array of integers? We could just alter the test for replacing the biggest so far, and we should make sure we alter the variable name as well. Altering code while keeping a variable name which now no longer reflects how it is used is a very bad thing to do. The code may work correctly, but it would be very confusing to a human who was looking at the code and trying to work out how it worked, maybe to modify or debug it. Imagine you were debugging someone else's code and a variable called biggestSoFar actually held the smallest so far. So, altering the test, and altering the method name to reflect what it now does, and altering the lcoal variable name to make it correctly meaningful in its new context gives us:

static int smallest(int[] a)
{ 
 int smallestSoFar=a[0]; 
 for(int i=1; i<a.length; i++)    
    {  
     if(a[i]<smallestSoFar)        
        smallestSoFar=a[i];    
    } 
 return smallestSoFar;
}

static DrinksMachine cheapest(DrinksMachine[] a)
{  
 DrinksMachine cheapestSoFar=a[0];  
 for(int i=1; i<a.length; i++)        
    {         
     if(a[i].getPrice()<smallestSoFar.getPrice())        
        cheapestSoFar=a[i];
    } 
 return cheapestSoFar;
}

static String longest(String[] a)
{   
 String longestSoFar=a[0];   
 for(int i=1; i<a.length; i++)        
    {         
     if(a[i].length()>longestSoFar.length())
        longestSoFar=a[i];
    }
 return longestSoFar;
}

In the code folder there is a link to the file UseArrays16.java which gives the method for finding the position of the longest string in an array of strings, and a front end for running it.

The code which we saw previously for finding whether a particular integer is in in array of integers can also be generalised. Here is a method for finding whether a String is in an array of Strings:

public static boolean isIn(String[] a,String str)
{
 for(int i=0; i<a.length; i++)
    if(a[i].equals(str))
       return true;
 return false;
}

Here is the version which returns the position of the String if it is in the array, or -1 if it isn't:

public static int position(String[] a,String str)
{
 for(int i=0; i<a.length; i++)
    {
     if(a[i].equals(str))
        return i;
    }
 return -1;
}

We could generalise further by altering the test used. So the problem of finding the position of an item equal to a particular item can be considered just one case of the more general problem of finding an item with some particular quality. Essentially the same algorithm is used, go through the items one by one until you find one with the property you are looking for. Here, for example, is a method which takes an array of Strings and an integer and returns the position of the first String in the array with more letters than the integer, or -1 if no String in the array is longer than the integer:

public static int longerString(String[] a,int n)
{
 for(int i=0; i<a.length; i++)
    {
     if(a[i].length()>n)
        return i;
    }
 return -1;
}

Java gives us techniques for writing code which is much more general than what we have seen so far. This means that instead of writing lots of methods which essentially do the same thing, but differ in details such as the exact test between two items to establish which is “bigger”, we can have just one method where the test depends on the particular type of items in the array. We can also make the test itself a separate argument to the method rather than something fixed in the code. Since finding the ...est item from a collection is an operation which is needed in many situations, Java provides library code for us to do it, so we don't have to write our own code anyway.

Discussion on the topic of generalising, so that algorithms involving an ordering comparison between objects we do not have to write separate code for each type of object, will come later in this module. Also we will see how collections of a particular type of object can be sorted in different orderings by providing a separate Comparator object to do the ordering of individual pairs of objects. At this point it is important that you realise that we are looking at algorithms involving comparisons of integers using the numerical comparison operators, such as <, just concentrate on the basic idea of the algorithm. In practice, code for algorithms like this should be written using the more generalised comparison operators we will look at later.

The topic of recursion is covered in more detail later in this module. It is best considered there with the LispList abstract data type. It works better there because Lisp lists easily break into parts and that enables recursion to be considered more naturally. The recursion covered here does not break the array into parts, but instead it works by passing indexes which have the effect of breaking the array into parts. However, when we get to that topic, it may help to come back and look at these examples of recursion, in order to get a general feel for it.

The following method is a way of expressing what we saw done with loops previously. As you can see, it does not use a loop at all, instead it uses a separate “helper method”:

 public static int biggest(int[] a)
 {
  return biggest(a,a[0],1);
 }

 private static int biggest(int[] a,int biggestSoFar,int i)
 {
  if(i<a.length)
     if(a[i]>biggestSoFar)
        return biggest(a,a[i],i+1);
     else
        return biggest(a,biggestSoFar,i+1);
  else
     return biggestSoFar;
 }

The helper method above which takes three arguments rather than the one of the public method can be thought of as performing the following operation: “take an array of integers, an integer representing the biggest-so-far, and an integer representing a position in the array. If there is a bigger integer in the portion of the array after that position, return that bigger integer, otherwise return the biggest-so-far value”.

A loop can be converted to a recursive call in the way shown in this example. The test for exiting the loop (which is the negation of the test for continuing it) becomes the test for the “base case”, which is when the method does not make a recursive call. Variables used in the loop become parameters to the method. The base case retuns the value of the parameter which represents the variable which should hold the final result from the loop. There is no real benefit to converting a loop to tail recursion, it is given here just as an illustration of a recursive method. In fact, if recursion turns out to be tail recursion, it is beneficial to convert it to the equivalent loop. The algorithms are really equivalent, but there is extra work done in managing the method calls when it is expressed as tail recursion rather than as a loop.

In the code folder, the file UseArrays17.java gives code for solving this problem using tail recursion.

Now here is another method with a recursive helper method which solves the same problem:

 public static int biggest(int[] a)
 {
  return biggest(a,0);
 }

 private static int biggest(int[] a,int from)
 {
  if(from==a.length-1)
     return a[from];
  else
     {
      int biggestOfRest = biggest(a,from+1);
      if(a[from]>biggestOfRest)
          return a[from];
      else
          return biggestOfRest;
     }
 }

In the code folder, the file UseArrays18.java gives code for solving this problem using recursion as described above which is not tail recursion.

With the idea that we can have a helper method which finds the biggest integer in a section of the whole array, we can also consider a solution which uses binary recursion. This is where there a method makes two calls to the same method. Here it is:

 public static int biggest(int[] a)
 {
  return biggest(a,0,a.length);
 }

 private static int biggest(int[] a,int from,int to)
 {
  if(to==from+1)
     return a[from];
  else if(to==from+2)
     if(a[from]>a[from+1])
        return a[from];
     else
        return a[from+1];
  else
     {
      int mid=(from+to+1)/2;
      int biggest1=biggest(a,from,mid);
      int biggest2=biggest(a,mid,to);
      if(biggest1>biggest2)
         return biggest1;
      else
         return biggest2;
     }

This is an example where the code would look neater if we were to use Java's conditional operator. The conditional operator is something like an if-statement, but it forms an expression not a statement. It takes the form boolexpr ? expr1 : expr2. The expressions expr1 and expr2 must be of the same type, and boolexpr must be of type boolean (meaning it is something that evaluates to true or false). An expression made up like this can be used in any place where expr1 or expr2 could be used on its own. Using this structure doesn't make any difference to the performance of the code, it's just a way of cutting down on complex use of ifs and elses to make the code look neater and so easier to follow. This operator tends not to be used much, but sometimes people get to like it and use it a lot. That is generally not a good idea, because complex usage of it (with expr1 and/or expr2 themselves being conditional expressions) soon leads to code which is hard to follow. Here is a version of the helper method of the previous code which makes use of the conditional operator in a sensible way:

 private static int biggest(int[] a,int from,int to)
 {
  if(to==from+1)
     return a[from];
  else if(to==from+2)
     return a[from]>a[from+1] ? a[from] : a[from+1];
  else
     {
      int mid=(from+to+1)/2;
      int biggest1=biggest(a,from,mid);
      int biggest2=biggest(a,mid,to);
      return biggest1>biggest2 ? biggest1 : biggest2;
     }
 }

Note in the above example, the variables biggest1 and biggest2 are used to store the results of the recursive calls. Sometimes a variable is used to store a result just to help break the code into parts, but at other times it is necessary because the same value has to be used more than once. Consider the following, which is a way of writing the helper method for binary recursion given above but without the variables to store the results of the recursive calls. Instead, one of the recursive calls is made again to give the result that is returned by the method, even though the call will give the same value as it did when it was made with the same arguments in the test part of the if statement:

 private static int biggest(int[] a,int from,int to)
 {
  if(to==from+1)
     return a[from];
  else if(to==from+2)
     if(a[from]>a[from+1])
        return a[from];
     else
        return a[from+1];
  else
     {
      int mid=(from+to+1)/2;
      if(biggest(a,from,mid)>biggest(a,mid,to))
         return biggest(a,from,mid);
      else
         return biggest(a,mid,to);
     }
 }

Just to show what excessive use of the conditional operator can lead to, here is the same code but all done using the conditional operator rather than if-statements:

 private static int biggest(int[] a,int from,int to)
 {
  int mid=(from+to+1)/2;
  return to==from+1 ? a[from] :
     ( to==from+2 ?
         (a[from]>a[from+1] ? a[from] : a[from+1]) :
         (biggest(a,from,mid)>biggest(a,mid,to) ?
             biggest(a,from,mid) :
             biggest(a,mid,to)
         )
     );
 }

In the code folder, the file UseArrays19.java gives code for solving this problem using tail recursion, while the file UseArrays20.java shows the same algorithm but coded using the conditional operator. The file UseArrays21.java shows the example which is inefficient because of repeated recursive calls with the same argument where just saving the result and using the saved result would have worked. The file UseArrays22.java shows this as well, but it is given mainly to show how it is possible (but not advisable) to place expressions built using the conditional operator inside expressions built using the conditional operator.

The files UseArrays23.java and UseArrays24.java are given so that you can see the inefficiency caused by unnecessary repeated recursive calls. They are like UseArrays19.java and UseArrays21.java, but have been modified to include a count which is incremented by 1 every time two integers from the array are compared to see which is the biggest. This is done with a static variable called count in the class. A static variable is shared by all code in the class, so every method call accesses the same variable when this name is used. In most cases this is bad practice, it is easy to lose track of how methods are interacting if they do so not just by what they take and return but also by using and changing shared variable. However, this is one example where it is a useful technique, since the shared variable enables a count easily to be made, and keeps the code which does this simple without much change needed to the original code to add it.

Last modified: 22 February 2019