Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 4 of 4

Thread: Using Comparable in Binary Search

  1. #1
    Junior Member
    Join Date
    Aug 2011
    Posts
    18
    Thanks
    2
    Thanked 0 Times in 0 Posts

    Default Using Comparable in Binary Search

    So I have written some code which tells whether a certain Integer is within a list of integers. I tried to do this with a comparable type instead of 'integer' type, but I realised that this wouldn't work as we could have say a String and Integer in the same list. I want to be able to have comparables of all the same type, but not limited to just Integers... Does anyone know how I could do this? I'm not very confident with using interfaces as input parameters. This is my code:

    package Recursion;
     
    import java.util.ArrayList;
    import java.util.List;
    import java.util.Scanner;
     
    public class BinarySearch {
    	// Takes in a sorted list (ascending order) of comparable objects 
    	// and finds whether a certain object is in that list using binary 
    	// search method.
     
    	public static void main(String[] args){
    		ArrayList<Integer> l = new ArrayList<Integer>();
    		l.add(3);
    		l.add(10);
    		l.add(30);
    		l.add(502);
    		System.out.println(l);
    		Scanner s = new Scanner(System.in);
    		while(s.hasNextInt()){
    			int n = s.nextInt();
    			System.out.print(BinarySearch.search(l, n));
    		}
    	}
     
    	//Check whether something is in the list
    	public static boolean search(List<Integer> al, Integer c){
    		//Current one we are looking at
    		Integer pivot = al.get(al.size()/2);
     
    		if (c.equals(pivot)){
    			return true;
    		} else if (c.compareTo(pivot) == -1){
    			if (al.size()/2 == 0){ //if our pivot is the first value in the sorted list
    				return false; // no more to see		
    			} else {
    				return search(al.subList(0,al.size()/2),c);
    			}
    		} else {
    			if(al.size()/2 == 0){
    				return false;
    			} else {
    			return search(al.subList(al.size()/2,al.size()),c); 
    			}
    		}
     
    	}
     
    }


  2. #2

    Default Re: Using Comparable in Binary Search

    The comparable interface will assist you in comparing objects.

    Comparable (Java 2 Platform SE v1.4.2)

    You will need to implement the methods in your class BinarySearch when you add the interface. You will create the rules in method compareTo() for when a certain BinarySearch is different from another. Be sure to read the rules in the link.
    Kenneth Walter
    Software Developer
    http://kennywalter.com

  3. #3
    Junior Member
    Join Date
    Aug 2011
    Posts
    18
    Thanks
    2
    Thanked 0 Times in 0 Posts

    Default Re: Using Comparable in Binary Search

    I understand that I have to implement the interface to use a data type as a 'comparable'.. however this is not my issue. The issue is that I want my list to contain any type which implements comparable, but I want it to be so only one type can be in the list at a time. For example, I could use this code to make and search a list of Integers as they are comparable, or a list of Strings, but I dont want to be able to have integers and strings in the same list.

    By making the input list type List<Comparable> this doesnt force the elements to be of one comparable type, but various types.

  4. #4
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: Using Comparable in Binary Search

    I would suggest using a Comparator instead.

Similar Threads

  1. Binary Search Help
    By OwsumEmam in forum What's Wrong With My Code?
    Replies: 7
    Last Post: March 31st, 2011, 11:01 PM
  2. Binary Search Help!
    By Allicat in forum What's Wrong With My Code?
    Replies: 8
    Last Post: March 15th, 2011, 04:03 PM
  3. Binary Search Tree
    By lex25288 in forum Algorithms & Recursion
    Replies: 3
    Last Post: January 19th, 2011, 09:10 AM
  4. Binary Search Loop
    By Tarakara in forum What's Wrong With My Code?
    Replies: 1
    Last Post: December 29th, 2010, 09:22 AM
  5. Binary Search Tree
    By Koren3 in forum What's Wrong With My Code?
    Replies: 9
    Last Post: November 12th, 2009, 09:27 AM