---

LAB 6 - BINARY SEARCH

---

NOTE: This Lab is somewhat simpler in view of the fact that you may wish to be practicing many other programs for the coming Lab Exam.
You are supposed to finish this and all other pending labs (if any) by this week.

NOTE: You must work on this problem using the receive and submit commands:

~kayaln/esc101/client/receive.pl :
To receive the P61.java file
~kayaln/esc101/client/submit.pl :
To submit your P61 solution. You will receive a score (possibly after some delay).

The following description is also available in the problem file you receive.

---

Binary Search is a standard algorithm for searching ordered lists. You will find a discussion of binary search at this web page. The objective of this homework is to explore recursive algorithms by implementing a recursive version of Binary Search.

Define a class StringArray. It should contain an array of strings stored in sorted order. There should be a constructor: StringArray () which creates an empty array of Strings as the default construct. A second constructor StringArray (String[] ss) should create an object with the value as in the array ss. A string array can be created with

String[] ss = {"a", "b", "c"};
In addition, you must also define the methods

• add(String s) which adds s to the array, and
• addAll(String[] ss) which adds the array ss to the end of the previous array.

Now define the following methods in this class:

• int binarySearch (String lookup)
• int binarySearch (String lookup, boolean caseIgnore)

The first method above takes a String argument : lookup and searches for a match in the array of Strings in this. It should return the first position in the array where the String lookup appears, if it appears at all. Otherwise it returns -1.

The second method performs the same task except that it ignores the case of the input String lookup while comparing it with members of the array in this. Please look at the "String" class in the JAVA API (under the "Literature" link) for a suitable method to use for this purpose.

---

Evaluation: Your method will be evaluated by defining different objects of the class StringArray. Let dictionary be an object of the class StringArray and the words be stored in the array wordlist in the class. Say:

1. wordlist[0]="Apple"
2. wordlist[1]="Ball"
3. wordlist[2]="Cat"
4. wordlist[3]="Donkey"
5. wordlist[4]="ball"
6. wordlist[5]="enough"

Then

1. dictionary.binarySearch("Ball") would return 1.
2. dictionary.binarySearch("ball") would return 4.
3. dictionary.binarySearch("BALL") would return -1.
4. dictionary.binarySearch("BALL",true) would return 1.

Also, we will look at your code for style (indentation, variable names, etc.) The program must be written using recursive calls.

---