Results 1 to 9 of 9
  1. #1
    TopNFalvors is offline Member
    Join Date
    Mar 2011
    Posts
    41
    Rep Power
    0

    Default binary search...multiple datatypes?

    I've seen a lot of examples of binary search functions, but can't find an example that allows for the use of multiple data types.

    Would it be possible to have a binary search that allows for both integer and strings?

    Thanks!

    Here is one example I found that allows for integers:

    Java Code:
    public class BinarySearch2
    {
        public static final int NOT_FOUND = -1;
        
        /**
         * Performs the standard binary search
         * using two comparisons per level.
         * @return index where item is found, or NOT_FOUND.
         */
        public static int binarySearch2( Comparable [ ] a, Comparable x )
        {
            int low = 0;
            int high = a.length - 1;
            int mid;
    
            while( low <= high )
            {
                mid = ( low + high ) / 2;
    
                if( a[ mid ].compareTo( x ) < 0 )
                    low = mid + 1;
                else if( a[ mid ].compareTo( x ) > 0 )
                    high = mid - 1;
                else
                    return mid;
            }
    
            return NOT_FOUND;     // NOT_FOUND = -1
        }
    
        // Test program
        public static void main( String [ ] args )
        {
            int SIZE = 8;
            Comparable [ ] a = new Integer [ SIZE ];
            for( int i = 0; i < SIZE; i++ )
                a[ i ] = new Integer( i * 2 );
    
            for( int i = 0; i < SIZE * 2; i++ )
                System.out.println( "Found " + i + " at " +
                                     binarySearch2( a, new Integer( i ) ) );
    
        }
    }

  2. #2
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,004
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by TopNFalvors View Post
    I've seen a lot of examples of binary search functions, but can't find an example that allows for the use of multiple data types.

    Would it be possible to have a binary search that allows for both integer and strings?
    Sure you can do that; you have to define the order between Integers and Strings, say all Integers are less than Strings. Use a Comparator<Object> to do the job. If it has to compare two objects that don't have the same type return -1 if it compares an Integer and a String, +1 if it compares a String and an Integer; otherwise it compares two things of the same type; compare the two objects as usual.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  3. #3
    TopNFalvors is offline Member
    Join Date
    Mar 2011
    Posts
    41
    Rep Power
    0

    Default

    I tried using generics like this:

    Java Code:
    public int searchBinary3(T value, int val1, int val2, T[] a)
    but then when I tried to compare using "<" or ">" it would give me an error saying that those operators cannot be applied to "T".

    Thanks!

  4. #4
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,004
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by TopNFalvors View Post
    I tried using generics like this:

    Java Code:
    public int searchBinary3(T value, int val1, int val2, T[] a)
    but then when I tried to compare using "<" or ">" it would give me an error saying that those operators cannot be applied to "T".

    Thanks!
    I don't understand what you're trying to do there; You can only compare Objects (Strings or Integers) or primitives (ints etc.) You need a simple compareTo(Object a, Object b) method that compares Strings and/or Integers, just as I described in my first reply. Leave out those generics; you don't need them

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  5. #5
    TopNFalvors is offline Member
    Join Date
    Mar 2011
    Posts
    41
    Rep Power
    0

    Default

    Oh ok...but I thought with newer Java, you should use generics?

  6. #6
    TopNFalvors is offline Member
    Join Date
    Mar 2011
    Posts
    41
    Rep Power
    0

    Default

    Another thing...generics or not...how can the same code compare the contents of both string and integer arrays?

    Thanks!

  7. #7
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,004
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by TopNFalvors View Post
    Another thing...generics or not...how can the same code compare the contents of both string and integer arrays?

    Thanks!
    That's not another thing, that was your original question; see my first reply.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  8. #8
    TopNFalvors is offline Member
    Join Date
    Mar 2011
    Posts
    41
    Rep Power
    0

    Default

    I need to loop through an array, and check to see if certain items are in the array.

    But the array could be integer or string...I got it to work with integers like this, but it won't work with strings:

    Java Code:
    public int SearchArray(T[] a, T index, int low, int high) {
      		
    		result = 0;
    
    		while (low <= high)
    		{		
          	mid = (low + high) / 2;
          
    		   result = mid;
    						
    			if (a[mid].compareTo(index) < 0)
    				low = mid + 1;
    			else if (a[mid].compareTo(key) > 0)
    				high = mid - 1;
    	 		else
    				return mid;  
    		}
    		return -1;
    	}
    Thanks!

  9. #9
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,004
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by TopNFalvors View Post
    I need to loop through an array, and check to see if certain items are in the array.

    But the array could be integer or string...I got it to work with integers like this, but it won't work with strings:
    As I wrote before: you have to write your own compareTo( ... ) method; something like this:

    Java Code:
    int compareTo(Object a, Object b) {
       if ((a instanceof Integer) == (b instanceof String))
          if (a instanceof Integer)
             return -1;
          else
             return 1;
    
       if (a instanceof Integer)
          return ((Integer)a).compareTo((Integer)b);
       else
          return ((String)a).compareTo((String)b);
    }
    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

Similar Threads

  1. Binary Search
    By cengho in forum Java Applets
    Replies: 4
    Last Post: 12-24-2010, 10:26 AM
  2. Binary Search Help
    By Plissken in forum New To Java
    Replies: 2
    Last Post: 03-13-2010, 10:34 AM
  3. Binary search tree search method
    By chopo1980 in forum New To Java
    Replies: 2
    Last Post: 12-10-2009, 01:42 AM
  4. Recursive Binary Search
    By EternalSolitude in forum New To Java
    Replies: 2
    Last Post: 11-21-2008, 06:26 AM
  5. binary search
    By tranceluv in forum New To Java
    Replies: 10
    Last Post: 01-14-2008, 07:13 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •