A recursive implementation!

Exercise Implement find according to the binary search algorithm. Assume the students array is sorted.

Solution

Here is a recursive version of find that implements Binary Search:

// Binary Search
// Assumption:
// - students' emails are unique
// - students array is sorted (based on emails)
public Student find(String email) {
  // delegate to the helper find method!
  return find(email, 0, numStudents - 1);
}

// helper: recursive binary search
private Student find(String email, int first, int last) {
  // we use first and last indicies to narrow the attention
  // on a portion of the students array. For example:
  // to search only in the first 5 elements: find(email, 0, 6);
  // to search the entire array: find(email, 0, numStudents - 1); 

  // base case
  if (last < first) { // no more element to search
    return null; // if we are here, the target is not in this roster
  }

  int mid = (first + last) / 2;

  if (email.compareTo(students[mid].getEmail()) == 0) {
    // found it!
    return students[mid];
  } else if (email.compareTo(students[mid].getEmail()) > 0) {
    // ignore the first half
    // repeat the search for the second half
    // look in the students array but start from mid point
    return find(email, mid + 1, last);
  } else  {
    // ignore the second half
    // repeat the search for the first half
    // look in the students array from start up to mid point
    return find(email, first, mid - 1);
  }
}

Note that find makes use of a private helper method (also called) find:

  • The two find methods share a name but have a different set of parameters; this is called method overloading, which allows you to reuse a method name.

  • The helper find is declared as a private method; this means any client of Roster (other classes/code/program that use Roster) cannot directly access it.

Information Hiding Principle: To prevent certain aspects of a class (or software component) from being accessible to its clients.

Information hiding shifts the code's dependency onto a well-defined interface. For example, clients of the Roster class would use find with one parameter email irrespective of whether find implements the linear or binary search.

Another common way where information hiding manifests itself is by making your class attributes (fields) inaccessible from the outside while providing getter and setter methods for attributes that shall be readable/updatable by other classes.

Java supports access modifiers (like private) that you can use to observe information hiding principle.

Resources