# binary search...multiple datatypes?

• 03-15-2011, 03:50 PM
TopNFalvors
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:

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 ) ) );     } }```
• 03-15-2011, 04:06 PM
JosAH
Quote:

Originally Posted by TopNFalvors
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
• 03-15-2011, 04:32 PM
TopNFalvors
I tried using generics like this:

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!
• 03-15-2011, 05:08 PM
JosAH
Quote:

Originally Posted by TopNFalvors
I tried using generics like this:

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
• 03-15-2011, 06:56 PM
TopNFalvors
Oh ok...but I thought with newer Java, you should use generics?
• 03-15-2011, 07:32 PM
TopNFalvors
Another thing...generics or not...how can the same code compare the contents of both string and integer arrays?

Thanks!
• 03-15-2011, 08:07 PM
JosAH
Quote:

Originally Posted by TopNFalvors
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
• 03-15-2011, 08:20 PM
TopNFalvors
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:

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!
• 03-15-2011, 09:03 PM
JosAH
Quote:

Originally Posted by TopNFalvors
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:

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