Binary Search and Generics

Question

I am finishing up my project but I can not getting the answer that I need. This is what I have.

public class Question1<T extends Comparable>
{
private static Circle[] b = {};
private T key;

public Question1(Circle[] b, T key)
{
    Question1.b = b;
    this.key = key;
}


/**
 * @param aB the b to set
 */
public static void setB(Circle[] aB) {
    b = aB;
}
/**
 * @param key the key to set
 */
public void setKey(T key) {
    this.key = key;
}

/**
 *
 * @param b
 * @param low
 * @param high
 * @param x
 * @return 
 */
public String run(Circle[] b, int low, int high,int x)
{
    if(low > high)
    {
        return "This is not a Circle.";
    }
    else 
    {
        int mid = ((high + low)/2);
        if(key.compareTo(b[mid].radius) == 1)
        {
            return run(b,mid+1,high,x++);
        }
        else if( key.compareTo(b[mid].radius) == 0)
        {
            return run(b,low,mid-1,x++);
        }
        return "You wanted to find Circle: " + key + " It is in element: " + b[x];
    }
 }
}

Here is the circle object class with the compareTo() method

public class Circle implements Comparable<Circle>
{
  public double radius;
  public Circle() {
  }

public Circle(double r)
{
    this.radius = r;
}
public void setRadius(double radius)
{
    this.radius = radius;
}
@Override
public String toString()
{
    return " " + radius;
}
/**
 *
 * @param t
 * @return
 */
@Override
public int compareTo(Circle t)
{
    if(this.radius < t.radius)
    {
        return 1;
    }
    else if(this.radius > t.radius)
    {
        return 0;
    }
    return 2;
}
}

Here is my start method

public class Start 
{
public static void main(String[] args)
{
    Circle[] b = {new Circle(1),new Circle(2),new Circle(3),new Circle(4),new Circle(5),new Circle(6)};
    double key = 4;
    Question1 qu = new Question1(b,key);

    System.out.println(qu.run(b, 0, b.length,0));
}
}

The problem is when I start comparing the radii. lets say I create an array of circles

Circle[] b = {new Circle(1),new Circle(2),new Circle(3),new Circle(4),new Circle(5),new Circle(6)};

I want to find a circle with radii of 4. but my code doesn't find it and goes to "this is not a circle" what I think it is that I have not coded the compareTo method correctly. If not what can I do to correct what is happening?

Answer 1

You are trying to do a binary search (using the radius of the circle), and had a few problems.

1. Circle compareTo:

Use the Double compare method:

@Override
public int compareTo(Circle t) {
    return Double.compare(this.radius, t.radius);
}

2. Run method

Wrong use of compare; replace with

public String run(Circle[] b, int low, int high, int x) {
    if (low > high || ((low == high) && high >= b.length)) {
        return "This Circle is not found.";
    } else {
        int mid = ((high + low) / 2);
        if (key.compareTo(b[mid].radius) == 0)
            return "You wanted to find Circle: " + key + " It is in element: " + mid;
        if (key.compareTo(b[mid].radius) > 0) {
            return run(b, mid + 1, high, x++);
        } else {
            return run(b, low, mid - 1, x++);
        }
    }
}

With these changes, the search finds all of the circles in your test array, and works for cases where the radius is less than the lowest, or higher than the highest.

I am not sure what you are trying to do with variable x? Perhaps count how many iterations it takes to find the key? But you don't use it.