The Java Course provides a general introduction to programming in Java. It is based on A.B. Downey's book, How to Think Like a Computer Scientist. Click here for details. 
Home Arrays of Objects Searching  
Search the VIAS Library  Index  
Searching
The next method I want to write is findCard, which searches through an array of Cards to see whether it contains a certain card. It may not be obvious why this method would be useful, but it gives me a chance to demonstrate two ways to go searching for things, a linear search and a bisection search. Linear search is the more obvious of the two; it involves traversing the deck and comparing each card to the one we are looking for. If we find it we return the index where the card appears. If it is not in the deck, we return 1. public static int findCard (Card[] deck, Card card) {for (int i = 0; i< deck.length; i++) { if (sameCard (deck[i], card)) return i; } return 1; } The arguments of findCard are named card and deck. It might seem odd to have a variable with the same name as a type (the card variable has type Card). This is legal and common, although it can sometimes make code hard to read. In this case, though, I think it works. The method returns as soon as it discovers the card, which means that we do not have to traverse the entire deck if we find the card we are looking for. If the loop terminates without finding the card, we know the card is not in the deck and return 1. If the cards in the deck are not in order, there is no way to search that is faster than this. We have to look at every card, since otherwise there is no way to be certain the card we want is not there. But when you look for a word in a dictionary, you don't search linearly through every word. The reason is that the words are in alphabetical order. As a result, you probably use an algorithm that is similar to a bisection search:
If you ever get to the point where there are two adjacent words on the page and your word comes between them, you can conclude that your word is not in the dictionary. The only alternative is that your word has been misfiled somewhere, but that contradicts our assumption that the words are in alphabetical order. In the case of a deck of cards, if we know that the cards are in order, we can write a version of findCard that is much faster. The best way to write a bisection search is with a recursive method. That's because bisection is naturally recursive. The trick is to write a method called findBisect that takes two indices as parameters, low and high, indicating the segment of the array that should be searched (including both low and high).
Steps 3 and 4 look suspiciously like recursive invocations. Here's what this all looks like translated into Java code: public static int findBisect (Card[] deck, Card card, int low, int high) {int mid = (high + low) / 2; int comp = compareCard (deck[mid], card); if (comp == 0) { return mid; } else if (comp > 0) { return findBisect (deck, card, low, mid1); } else { return findBisect (deck, card, mid+1, high); } } Rather than call compareCard three times, I called it once and stored the result. Although this code contains the kernel of a bisection search, it is still missing a piece. As it is currently written, if the card is not in the deck, it will recurse forever. We need a way to detect this condition and deal with it properly (by returning 1). The easiest way to tell that your card is not in the deck is if there are no cards in the deck, which is the case if high is less than low. Well, there are still cards in the deck, of course, but what I mean is that there are no cards in the segment of the deck indicated by low and high. With that line added, the method works correctly: public static int findBisect(Card[] deck, Card card, int low, int high) { System.out.println (low + ", " + high); if (high < low) return 1; int mid = (high + low) / 2; int comp = deck[mid].compareCard (card); if (comp == 0) { return mid; } else if (comp > 0) { return findBisect (deck, card, low, mid1); } else { return findBisect (deck, card, mid+1, high); } } I added a print statement at the beginning so I could watch the sequence of recursive calls and convince myself that it would eventually reach the base case. I tried out the following code: Card card1 = new Card (1, 11);System.out.println (findBisect (deck, card1, 0, 51)); And got the following output: 0, 510, 24 13, 24 19, 24 22, 24 23 Then I made up a card that is not in the deck (the 15 of Diamonds), and tried to find it. I got the following: 0, 510, 24 13, 24 13, 17 13, 14 13, 12 1 These tests don't prove that this program is correct. In fact, no amount of testing can prove that a program is correct. On the other hand, by looking at a few cases and examining the code, you might be able to convince yourself. The number of recursive calls is fairly small, typically 6 or 7. That means we only had to invoke compareCard 6 or 7 times, compared to up to 52 times if we did a linear search. In general, bisection is much faster than a linear search, especially for large arrays. Two common errors in recusive programs are forgetting to include a base case and writing the recursive call so that the base case is never reached. Either error will cause an infinite recursion, in which case Java will (eventually) throw a StackOverflowException.


Home Arrays of Objects Searching 