In a previous set of notes we covered loops which went through a whole array, one element at a time. For each element some operation was performed. A general pattern for this was:
for(int i=0; i<a.length; j++)The
dosomething
dosomething here could be any Java statement,
including several statements made into one by starting with {
and finishing with }.
false. Then we could loop through
the array using the pattern above, and at any point where a[i]
is equal to the integer, set the boolean variable to true.
So our dosomething, supposing the boolean variable
is called found and the integer we are looking for is
stored in
a variable called n, is:
if(a[i]==n)Here is this code put into a static method, with the initialisation of
found=true;
found:
public static boolean member(int n,int[] a)In order that you can test this method, here is a simple program that makes use of it:
{
boolean found=false;
for(int i=0; i<a.length; i++)
if(a[i]==n)
found=true;
return found;
}
import java.util.*;Please remember, as usual, the important thing here is not the whole program, but the method which demonstrates the loop pattern we are interested in. You might like to note, however, that as this method returns a
import java.io.*;
class Member1
// A program to read a list of numbers then read one number and
// say whether it is in the list
{
public static void main(String[] args) throws IOException
{
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
System.out.println("Enter a list of numbers (all on one line):");
int[] a = readNumbers(in);
System.out.print("Enter a number: ");
int n = readANumber(in);
if(member(n,a))
System.out.println("The number is in the list");
else
System.out.println("The number is not in the list");
}
public static int[] readNumbers(BufferedReader in) throws IOException
{
String line = in.readLine();
StringTokenizer toks = new StringTokenizer(line);
int[] a = new int[toks.countTokens()];
for(int i=0; i<a.length; i++)
a[i] = Integer.parseInt(toks.nextToken());
return a;
}
public static int readANumber(BufferedReader in) throws IOException
{
String line = in.readLine();
int n = Integer.parseInt(line);
return n;
}
public static boolean member(int n,int[] a)
{
boolean found=false;
for(int i=0; i<a.length; i++)
if(a[i]==n)
found=true;
return found;
}
}
boolean value we can put a call to it directly
in the test part of an if-statement. The if-statement above that is
written:
if(member(n,a))could be written with a separate variable to hold the result of the method call:
System.out.println("The number is in the list");
else
System.out.println("The number is not in the list");
boolean flag=member(n,a);but there is no need for this, unless for some reason we wanted to save the value of the call
if(flag)
System.out.println("The number is in the list");
else
System.out.println("The number is not in the list");
member(n,a) for use at a
later stage. Declaring a variable whose only purpose is to hold the
result of a method call which is then immediately used in the next
statement doesn't make much sense. You might as well put the method
call in the place where you would put the variable, it means the same
thing but makes the code easier to understand because there is less
detail to follow. The one time when you might want to declare a
separate variable like this (apart from cases where you need to use
the result of the method call somewhere else as well) is when you
have a very complicated expression, maybe a method call as an argument
to a method call, which itself is an argument to a method call, ...,
and so on. In this case the use of variables declared just to
temporarily hold values may help break up a complicated expression
into smaller parts which makes it easier to understand.
member goes through
the whole array, but there is no need for it to do so. Once it
has found the number it is searching for, there is no need for it
to go further in the array, it can immediately return true.
One way we could do this is to use the Java break
statement, making the member method:
public static boolean member(int n,int[] a)The effect of executing a
{
boolean found=false;
for(int i=0; i<a.length; i++)
if(a[i]==n)
{
found=true;
break;
}
return found;
}
break statement is that
execution
of the loop it is in is immediately halted, and the statement following
the loop is executed next. In the above example, this means the loop
is exited when a[i] has the value equal to n,
even though the continuation condition in the loop header,
i<a.length remains true. The break
statement here is inside the if-statement, which is inside the loop.
In fact, it only makes sense for a break statement to be
inside an if-statement inside a loop, since if it wasn't inside an
if-statement, it would always be executed, and the loop would always be
exited on the first time round it. The structure of the code above
could be shown diagrammatically as:
We call this an "interrupted loop" because the loop may be exited
before the conditions indicated in its header for exiting are
reached (in this case, i<a.length becoming
false, i.e. we have gone through the whole array).
Interrupting a loop with a break is sometimes a good
way to express a problem, but it's a technique that should be used
with caution. In particular, it should not be used for loops with
large amounts of code inside the loop, since then it might be easy to
miss the fact that there's a break inside and the loop
could exit in conditions other than those indicated by the loop header.
Another way of dealing with this would be to indicate in the header
that we are leaving the loop either when found becomes
equal to true or when i becomes equal
to the length of the array. The condition given in the header of a
for-loop,
however, is the condition for continuing execution of the
loop, which is the negation of the condition for exiting it. We
continue the loop if found is not equal to true
and i is less than the length of the
array. We could write this as found!=true&i<a.length.
But since found is itself a boolean value, the expression
found!=true evaluates to true
only when found is false, and an easier
way of expressing the same thing is !found. Remember that
! is the way to write the logic operator "not" in Java.
This gives us the following code for the method:
public static boolean member(int n,int[] a)We could note here that since
{
boolean found=false;
for(int i=0; !found&i<a.length;!found; i++)
if(a[i]==n)
found=true;
return found;
}
found becomes true
when a[i] is equal to n and remains false
before that, we could test the value of a[i] against
n directly in the loop header. This would give us:
for(int i=0; a[i]!=n&i<a.length; i++)but then what would go into the body of the for-loop? The answer is "nothing". It is possible to have a for-loop which consists of just the header - or almost just the header. All that is required to complete it is a semi-colon at the end, in this case:
for(int i=0; a[i]!=n&i<a.length; i++);What this means is that the statement inside the for-loop is the "empty statement" in other words, the statement that does nothing and is written as nothing, but such a statement still has to have the semi-colon to end it. Diagrammatically, this could be shown as:
Another way, which is perhaps a little clearer, to write the empty
statement is {}.
There are two problems with loop proposed above. The first is how
can
we tell, when it terminates, whether we have found the integer we are
looking for or not. The answer is that the final value of i
tells us, since if it is less than a.length, the loop
has terminated because a[i]!=n is no longer true, that is
we have found a value of i such that a[i]
is
equal to n. If the final value of i is
a.length then i has run through all the
values
from 0 to the length of the array and not found a case where a[i]
is equal to n, so we can conclude that n
does
not occur in the array.
The second problem is that when we evaluate a[i]!=n&i<a.length
in the loop, we always evaluate both a[i]!=n and
i<a.length. But if we have gone through all the array
and i has reached the value a.length, there
is no array cell a[i], so attempting to evaluate
a[i]!=n will result in the program crashing (or, to be
technical, "throwing an IndexOutOfBoundsException"). To
avoid this, we can make use of Java's "short circuit" and operation,
written &&. This is defined as exp1&&exp2,
where exp1
and exp2 are any expressions that evaluate to
boolean
values, evaluating first exp1. If exp1
evaluates to false, the whole expression evaluates to
false without exp2 ever being
attempted. If exp1 evaluates to true,
then exp2 is evaluated and its result given as the
result of the whole expression exp1&&exp2.
Therefore, if we have i<a.length&&a[i]!=n,
first
i<a.length is evaluated, and if it evaluates to false,
i.e. i is equal to or greater than a.length,
then a[i]!=n is not evaluated at all, so it does not
matter
that i has a value which would cause any attempt to find
the
value of a[i] to cause the program to crach.
So we could write the loop:
for(int i=0; i<a.length&&a[i]!=n; i++) {}
but that still causes us problems. A for-loop lets us declare a
variable
in the initialisation part of the loop, as in int i=0
above. We have used this as the standard pattern for a loop that goes
through an array. But this means the variable declared is local
to the loop, we cannot access it outside the loop. That means we cannot
tell whether i has a value less than a.length
once the loop has finished. In order to be able to do this, we have to
declare i outside the loop. Putting this together gives
us the following revised code for the static method member:
public static boolean member(int n,int[] a)The
{
int i;
for(i=0; i<a.length&&a[i]!=n; i++) {}
return i<a.length;
}
{} indicates that the loop has only the empty
statement within it, so the following statement is not in the loop.
The whole code for the method could be shown diagrammatically as:
You might be surprised at the last statement, and wonder why it isn't:
if(i<a.length)The answer is that
return true;
else
return false;
i<a.length is a boolean expression
which evaluates to true or false, so we can
just
return its value. Whenever you're writing a method that returns a
boolean,
if you find yourself ending it with:
if(test)for any expression
return true;
else
return false;
test it's always neater to
write instead:
return test;
An alternative approach to this problem would be to note that executing
a return statement anywhere in a method causes the method
to be halted and the value given in the return statement to be returned
as the result of the method. So we could write the method as:
public static boolean member(int n,int[] a)So here, if
{
for(int i=0; i<a.length; i++)
if(a[i]==n)
return true;
return false;
}
a[i] is equal to n the
statement return true is executed, and even though
it is in the middle of the loop, the whole method terminates. Note
the structure of the code here could be shown as:
The statement return false; is outside the
for-loop, its in only executed and false returned by
the method if the loop goes through the whole array and terminates
with i equal to a.length. Note, do not
confuse
this with:
// Deliberately silly codewhich, for some reason, novice programmers often seem to write. In this case, each time round the loop, whenever
for(int i=0; i<a.length; i++)
if(a[i]==n)
return true;
else
return false;
a[i] equals n
the method terminates and returns true, and whenever
a[i] is not equal to n the method terminates
and returns false. In other words, the method terminates
and returns either true or false on every
time round it, so it will only be gone round once, returning
true if the first element in the array is equal to n
and returning false if the first element in the array is
not
equal to n. This can be shown diagrammatically as:
It is clearly not the desired behaviour, nor, since it only ever goes round the loop once or zero times, a piece of code that is ever sensible.
Last modified: 14 December 2004