Binary Search of array of objects

Question

I was given some code that contains an Array of Person objects I am to write methods to do the binary search and to override the compareto method in the Person class to compare based on last name and then first name.

public static int binarySearch( Person[] persons, Person key )
   {
      int low = 0;
      int high = persons.length - 1;

      return binarySearch(persons, key, low, high);
   }

   private static int binarySearch( Person[]persons, Person key, int low, int high )
   {
          if(low > high)        //The list has been exhausted without a match.
              return -low - 1;

          int mid = (low + high) / 2;
          if (persons[mid] == key)
              return mid;
          if(persons[mid] < key) //!!**'The < operator is undefined for the type'
              return binarySearch(persons, key, low, mid-1);
          else 
              return binarySearch(persons, key, 0, persons.length -1);
       }

I think I have most of the binary search code write. However, the problem I'm having is at if(persons[mid] < key) I get the error 'The < operator is undefined for the type'.

I thought it may have to do something with my compareTo method but I can't seem to fix it

Here is compareTo for reference

public int compareTo( Object o )
   {
      Person p = (Person) o;
      int d = getLastName().compareTo(p.getLastName());
      if (d == 0)
          d = getFirstName().compareTo(p.getFirstName());
      return d;
   }

Thanks for any and all help!

`if(persons[mid] < key) I get the error 'The < operator is undefined for the type'.` sure it is not `<` and `>` are not defined for `objects` — Prateek, Oct 16 '13 at 18:59

score 1 · Answer 1 · answered Oct 16 '13 at 18:51

1

instead of

if(persons[mid] < key)

use

if(persons[mid].compareTo(key) < 0)

answered Oct 16 '13 at 18:51

jmj

237,923
42
401
438

score 1 · Answer 2 · answered Oct 16 '13 at 18:54

Try this:

int mid = (low + high) / 2;
if (persons[mid].compareTo(key) == 0)
    return mid;
if(persons[mid].compareTo(key) < 0)
    return binarySearch(persons, key, low, mid-1);
else 
    return binarySearch(persons, key, 0, persons.length -1);

You can not compare Objects using < > like operators.

GIIRRII · Answer 3 · 2017-06-20T11:17:19.107

You are comparing two object references which holds nothing but the bit pattern which points to the location of actual person object. For object comparison you need to define on what properties (attributes) you want to compare them. so try this

    if (persons[mid].compareTo(key) == 0)
        return mid;
    if(persons[mid].compareTo(key) < 0)

also check correct implementation for binarySearch.

     return binarySearch(persons, key, mid +1, high);
else
     return binarySearch(persons, key, low, mid -1);

And you haven't used this in your compareTo. It should have been like

public int compareTo( Object o )
   {
      Person p = (Person) o;
      int d = this.getLastName().compareTo(p.getLastName());
      if (d == 0)
          d = this.getFirstName().compareTo(p.getFirstName());
      return d;
   }

also is your persons array sorted ?

Binary Search of array of objects

3 Answers3