1. Member
Join Date
Mar 2011
Posts
41
Rep Power
0

## 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. 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

3. Member
Join Date
Mar 2011
Posts
41
Rep Power
0
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. Originally Posted by TopNFalvors
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

5. Member
Join Date
Mar 2011
Posts
41
Rep Power
0
Oh ok...but I thought with newer Java, you should use generics?

6. Member
Join Date
Mar 2011
Posts
41
Rep Power
0
Another thing...generics or not...how can the same code compare the contents of both string and integer arrays?

Thanks!

7. 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

8. Member
Join Date
Mar 2011
Posts
41
Rep Power
0
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. 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:

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

#### Posting Permissions

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