/**
 * Search algorithms for arrays of cards.
 */
public class Search {

    /**
     * Sequential search.
     */
    public static int search(Card[] cards, Card target) {
        for (int i = 0; i < cards.length; i++) {
            if (cards[i].equals(target)) {
                return i;
            }
        }
        return -1;
    }

    /**
     * Binary search (iterative version).
     */
    public static int binarySearch(Card[] cards, Card target) {
        int low = 0;
        int high = cards.length - 1;
        while (low <= high) {
            System.out.println(low + ", " + high);

            int mid = (low + high) / 2;                   // step 1
            int comp = cards[mid].compareTo(target);

            if (comp == 0) {                              // step 2
                return mid;
            } else if (comp < 0) {                        // step 3
                low = mid + 1;
            } else {                                      // step 4
                high = mid - 1;
            }
        }
        return -1;
    }

    /**
     * Binary search (recursive version).
     */
    public static int binarySearchRec(Card[] cards, Card target,
                                      int low, int high) {
        System.out.println(low + ", " + high);

        if (high < low) {
            return -1;
        }
        int mid = (low + high) / 2;                       // step 1
        int comp = cards[mid].compareTo(target);

        if (comp == 0) {                                  // step 2
            return mid;
        } else if (comp < 0) {                            // step 3
            return binarySearchRec(cards, target, mid + 1, high);
        } else {                                          // step 4
            return binarySearchRec(cards, target, low, mid - 1);
        }
    }

    /**
     * Make an array of 52 cards.
     */
    public static Card[] makeDeck() {
        Card[] cards = new Card[52];
        int index = 0;
        for (int suit = 0; suit <= 3; suit++) {
            for (int rank = 1; rank <= 13; rank++) {
                cards[index] = new Card(rank, suit);
                index++;
            }
        }
        return cards;
    }

    /**
     * Demonstrates how to call the search methods.
     */
    public static void main(String[] args) {
        Card[] cards = makeDeck();
        Card jack = new Card(11, 0);
        Card fake = new Card(15, 1);

        System.out.println("Sequential search");
        System.out.println(search(cards, jack));
        System.out.println();

        System.out.println("Binary search");
        System.out.println(binarySearch(cards, jack));
        System.out.println();

        System.out.println("Failed binary search");
        System.out.println(binarySearch(cards, fake));
        System.out.println();

        System.out.println("Recursive binary search");
        System.out.println(binarySearch(cards, jack));
        System.out.println();
    }
}

@@ -646,32 +646,35 @@
                 
+   
 // step 1%0A      
@@ -771,32 +771,35 @@
                 
+   
 // step 2%0A      
@@ -870,32 +870,35 @@
                 
+   
 // step 3%0A      
@@ -934,32 +934,35 @@
         %7D else %7B
+   
                 
@@ -1414,32 +1414,35 @@
                 
+   
 // step 1%0A      
@@ -1535,32 +1535,35 @@
                 
+   
 // step 2%0A      
@@ -1602,32 +1602,35 @@
  if (comp %3C 0) %7B
+   
                 
@@ -1725,32 +1725,35 @@
         %7D else %7B
+   
                 

read through ch12