Computer Science 210
Data Structures

Fall 2017, Siena College

Home     Syllabus     Schedule     Examples     Style Guide

SearchExample BlueJ Project

Click here to download a BlueJ project for SearchExample.

SearchExample Source Code

The Java source code for SearchExample is below. Click on a file name to download it.

SearchExample.java

/**
 * Starter for in-class development of some search methods
 *
 * @author Jim Teresco, with the Fall 2017 CSIS 210 Class at Siena
 */

import java.util.Random;

public class SearchExample
{
    // a main method to try things out
    public static void main(String args[]) {
    Random r = new Random();
    final int NUM_INTS = 100;
    final int MAX_INCREMENT = 10;
    int[] orderedInts = new int[NUM_INTS];
    Integer[] orderedIntegers = new Integer[NUM_INTS];

    // we'll put some random but ascending numbers into our arrays
    int val = r.nextInt(MAX_INCREMENT) + 1;
    orderedInts[0] = val;
    orderedIntegers[0] = val;  // will be autoboxed

    for (int i = 1; i < NUM_INTS; i++) {
        val = orderedInts[i-1] + r.nextInt(MAX_INCREMENT) + 1;
        orderedInts[i] = val;
        orderedIntegers[i] = val;
    }
            
    // note these elements will each be autoboxed from double to Double
    Double[] orderedDoubles = { -10.5, -6.0, 0.0, 3.5, 9.1, 17.23 };
    
    // and Strings work too
    String[] orderedStrings = {
        "Alice", "Bob", "Carol", "David", "Ellen", "Frank", "Gloria",
        "Hal", "Isabelle", "Joey", "Kimberly", "Larry" };

    // but not Objects
    //Object[] objectTest = { 87, "Mary", 17.29 };
    //int bigObj = linearSearchMaxIndex(objectTest);
    
    // find largest int in orderedInts with a linear search
    int largeIndex = linearSearchMaxIndex(orderedInts);
    System.out.println("linear search found largest orderedInts " + 
        orderedInts[largeIndex] + " at index " + largeIndex);
        
    // find largest int in orderedIntegers with a linear search
    largeIndex = linearSearchMaxIndex(orderedIntegers);
    System.out.println("linear search found largest orderedIntegers " + 
        orderedIntegers[largeIndex] + " at index " + largeIndex);

    // find largest Double in orderedDoubles with a linear search
    largeIndex = linearSearchMaxIndex(orderedDoubles);
    System.out.println("linear search found largest orderedDoubles " + 
        orderedDoubles[largeIndex] + " at index " + largeIndex);
    
    // find largest String in orderedStrings with a linear search
    largeIndex = linearSearchMaxIndex(orderedStrings);
    System.out.println("linear search found largest orderedStrings " + 
        orderedStrings[largeIndex] + " at index " + largeIndex);
    }
    
    // find largest index in Comparable array with a linear search
    public static <T extends Comparable> int linearSearchMaxIndex(T a[]) {
        
        return linearSearchMaxIndex(a, 0);
    }
    
    // recursive helper method with extra parameter
    private static <T extends Comparable> int
         linearSearchMaxIndex(T a[], int startAt) {
             
        // base case
        if (a.length - 1 == startAt) {
            return startAt;
        }
        
        // recursive case
        int bestOfRest = linearSearchMaxIndex(a, startAt + 1);
        if (a[startAt].compareTo(a[bestOfRest]) > 0) {
            return startAt;
        }
        else {
            return bestOfRest;
        }
        
     }
    
    // our recursive linear search on ints
    public static int linearSearchMaxIndex(int a[]) {
        
        return linearSearchMaxIndex(a, 0);
    }
    
    // recursive helper method
    private static int linearSearchMaxIndex(int a[], int startAt) {
        
        // base case: look only at the last item
        if (startAt == a.length - 1) {
            return startAt;
        }
        
        // recursive case
        int bestOfRest = linearSearchMaxIndex(a, startAt + 1);
        if (a[startAt] > a[bestOfRest]) {
            return startAt;
        }
        else {
            return bestOfRest;
        }
    }
    
}