Java Reference
In-Depth Information
This gets us to the second match, for " bus " , and the algorithm proceeds. In gen-
eral, we find ourselves in one of three situations when we compare the current word
in list1 with the current word in list2 :
The words might be equal, in which case we've found a match that should be
included in the overlap and we should advance to the next word in each list.
The word from the first list might be alphabetically less than the word from the
second list, in which case we can skip it because it can't match anything in the
second list.
The word from the second list might be alphabetically less than the word from the
first list, in which case we can skip it because it can't match anything in the first list.
Thus, the basic approach we want to use can be described with the following
pseudocode:
if (word from list1 equals word from list2) {
record match.
skip word in each list.
} else if (word from list1 < word from list2) {
skip word in list1.
} else {
skip word in list2.
}
We can refine this pseudocode by introducing two index variables and putting this
code inside a loop:
i1 = 0.
i2 = 0.
while (more values to compare) {
if (list1.get(i1) equals list2.get(i2)) {
record match.
increment i1.
increment i2.
} else if (list.get(i1) less than list.get(i2)) {
increment i1.
} else {
increment i2.
}
}
This version of the pseudocode is now fairly close to actual code. First, we have to
figure out an appropriate loop test. We start the two index variables at 0 and incre-
ment one or both each time through the loop. Eventually we'll run out of values in
one or both lists, and when that happens there won't be any more matches to find. So,
Search WWH ::




Custom Search