CODEWITHSUNDEEP
javabinary-searchcomparator
Zahir Abas
Zahir Abas

Reputation: 143

finding minimum price list for an operator

Country Code List=   92,  445,  445,  966,   92,  445,  966,  966, 92
Price List =       0.99, 0.91, 0.92, 0.97, 0.93, 0.97, 0.92, 0.97, 1.0
Operator List=        A,    C,    A,    B,    C,    B,    A,    C,  A

I am supposed to find minimum price list and corresponding operator when user enter a country code. Country Code data can be duplicated. It is not Unique. e.g. as we don't know countrycode: 92 belongs to which operator, 92 can exist for operator A, B, or C in the countrycode List.

I have written the code below. but It has a problem,

Problem : i am able to sort CountryCode , but binarySearch in the following code can not figure out the minimum price list correspondingly. It always gives me random value which is not minimum price. Improvement for the following code will be appreciated. 

class Dog implements Comparator<Dog>, Comparable<Dog>{
   private int CountryCode; 
   private double Price;
   private String Operator;
   Dog(){
   }

   Dog( int c, double p, String o){
       CountryCode= c;
       Price= p;
       Operator=o;
   }

   public int getCountryCode(){
      return CountryCode;
   }

   public double getPrice(){
      return Price;
   }
   public String getOperator(){
          return Operator;
       }


   // Overriding the compareTo method
   public int compareTo(Dog d){

       return CountryCode- d.getCountryCode();
   }


   // Overriding the compare method to sort the age 
   public int compare(Dog d, Dog d1){
       return d.CountryCode - d1.CountryCode;     
   }




}


public class Ser {                          
/**                                     
 * @param args
 */
public static void main(String[] args) {
    // Takes a list o Dog objects
    ArrayList <Dog> list1 = new ArrayList<Dog>();

      list1.add(new Dog(92, 0.99 , "A"));
      list1.add(new Dog(445, 0.91 , "C"));
      list1.add(new Dog(445, 0.92 , "A"));
      list1.add(new Dog(966, 0.97 , "B"));
      list1.add(new Dog(92, 0.93 , "C"));
      list1.add(new Dog(445, 0.97 , "B"));
      list1.add(new Dog(966, 0.92, "A"));
      list1.add(new Dog(966,0.97, "C"));
      list1.add(new Dog(92,1.0, "A"));
      // Sorts the array list using comparator

      Collections.sort(list1, new Dog());

      for(Dog a: list1)//printing the sorted list of ages
          System.out.println(a.getCountryCode() +"  : "+
         a.getOperator()+"  : "+ a.getPrice());

     int index=  Collections.binarySearch(list1, new Dog ( 92,null,null));

      if (index>=0)
      System.out.println( list1.get(index).getOperator()+ " " + list1.get(index).getPrice());
      else
          System.out.println("No operator is availible");

}}

Upvotes: 0

Views: 566

Answers (2)

rolfl
rolfl

Reputation: 17707

You never sorted the list by price, so you should not expect to get the minimum price.

At first look, the list is sorted in order of the country code.

The order of the prices within each country code is random depending on both:

  • the unspecified order in which the original list was sorted...
  • the first value the binary search finds with the right country code....

rolfl

Edit:

You ask what the right approach should be.... there are three that come to mind:

  • Use Kent's suggestion of a pre-built hierarchy-structure that sorts the data on both dimensions (country/price), and then you can pull the data you want quickly.
  • change the comparator to sort by both country and price, then scan the list (instead of binary search), and return the first item with the right country.
  • change the comparator to sort by both country and price, then search using binary-search for the country (binary search will return any of the positions that have that country), and then scan backwards to find the lowest price.

Upvotes: 3

Kent
Kent

Reputation: 195039

If your requirement is: if find multiple Dogs with same countryCode, return the Dog with lowest price.

I suggest that you change your list design.

you could have a Map<Integer, List<Dog>> key is countryCode. of course, Map<Integer, TreeSet<Dog>> or guava MultiMap<Integer, Dog> would be fine as well.

If countryCodes are really countries, your map won't have more than 300 entries.

Then you can save that O(logn) binary-search. and use O(1) to get the list/collection/TreeSet of Dogs of same countryCode.

Then you could sort (O(nlogn) )the collection of Dog by price if it is not sorted.(you should impl the comparable interface and impl. the methods) and get the first/last Dog. Depends on your sorting order. You could also keep the collection sorted for later usage. If it is just one-time job, you even could go through the Dog collection and get the Dog with lowest price. O(n)

If you want to have operator with sorting too, write that information into your compareTo method implementation.

And if it like you said, there are only thousand of elements, you don't have to care about the performance so much, unless the min/max search would be done many many times. If in that case, when you fill the map, or even if with your approach, the list, build another map for min/max price of a countryCode. This will save a lot of time later. Apparently if you cache the min/max price, you have to maintain it if the map (or your list) was changed, or some Dog was modified. Anyway, you know your requirement best, you could choose the right way to go.

Finally, please read something about java naming convention. CountryCode, Price look like Class not fields.

Upvotes: 1

Related Questions