APCS: AP Computer Science A @sfhs

Searching an ArrayList of String

The starter code Seek.java will make a very short ArrayList<String> and you can add to the main list to test the methods that you will write:

1. A Linear Search
2. A Binary Search using iteration (loops)
3. A Binary Search using recursion.

{ import java.util.ArrayList; public class Seek {

  // instance variables - replace the example below with your own
  private ArrayList<String> list;
  public Seek(String[] arr)
  {
      list = new ArrayList<String>();
      for(String s:arr)
          list.add(s);
      sort();    
  }

  public void sort()
  {
      boolean sorted = false;
      while (!sorted)
      {
          sorted = true;
          for(int i=0; i < list.size()-1; i++)
          {
              if ( list.get(i).compareTo( list.get(i+1) ) > 0)
              {
                  sorted = false;
                  String temp = list.remove(i);
                  list.add(i+1, temp);
              }
          }
      }
  }	

  public String toString()
  {
      String s="";
      for(String next:list)
          s+= " " + next;
      return s;
  }
  public int linearSearch(String str)
  {
      // your code here
      return -1;
  }
  public int binarySearchLoop(String str)
  {
      // your code here
      return -1;
  }public int binarySearchRecursive(String str)
  {
      // your code here
      return -1;
  }
  public static void main(String[] args)
  {
      String[] strings = {"cat", "dog", "bicycle", "apple", "giraffe", "paper"};
      Seek seek = new Seek(strings);
      System.out.println( seek);
      int index1 = seek.linearSearch("apple");
      int index2 = seek.linearSearch("monkey");
      System.out.println( "index of apple (should be found): "+index1);
      System.out.println( "index of paper (should be found): " + seek.linearSearch("paper"));
      System.out.println( "index of monkey (should be -1, not found): "+index2);
      // add additional calls to binarySearchLoop and binarySearchRecursive below:
  }

}

}