aspose file tools*
The moose likes Beginning Java and the fly likes Generic Binary Search for Ints & Strings Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Java 8 in Action this week in the Java 8 forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Generic Binary Search for Ints & Strings" Watch "Generic Binary Search for Ints & Strings" New topic
Author

Generic Binary Search for Ints & Strings

Luke Stamper
Ranch Hand

Joined: Jun 19, 2011
Posts: 64
I found out my program was supposed to be generic and not two separate searches. Ugh. Can anyone help me get started or point me in the right direction?

Thanks in advance.

Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

If you declare your method something like


then whatever is passed in, you can call without ever having to know what the actual class is.
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7081
    
  16

Luke Stamper wrote:I found out my program was supposed to be generic and not two separate searches. Ugh. Can anyone help me get started or point me in the right direction?

Just to add to what Jeff said, you will need to make your numeric array an Integer[], not an int[]. You could provide a converter though.

Winston


Isn't it funny how there's always time and money enough to do it WRONG?
Artlicles by Winston can be found here
Luke Stamper
Ranch Hand

Joined: Jun 19, 2011
Posts: 64
So i'm lost and in over my head. I think i'm on the right track but I can't figure out how to take my generic arrays and pass them into the search method. Also I can't figure out how to create a for loop similar to lines 15-23 that will work with my generic arrays.
Am I doing anything right?



Luke Stamper
Ranch Hand

Joined: Jun 19, 2011
Posts: 64
Can anyone help me with this program? I am so lost.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 36575
    
  16
Apart from the fact that you are supposed to say
<T extends Comparable<? super T>>,
what is going wrong?

I think you are making the mistake of trying too much all at once. Forget all about ints for the time being, but create an Integer[], like thisYou don’t need to sort anything. If you are learning searching, then stick to the searching and leave out the sorting. You can always add the sorting later.

I think you need to write out the algorithm with a pencil, remembering there are 6 variables, not the 5 you have:
  • low
  • high
  • mid
  • array
  • sought
  • index
  • You need to pass the array as a parameter to that method, which should read like thisNote
  • 1: It is the method which should be generic, not the class
  • 2: The method does not use any instance variables, so ought to be static.
  • 3: You don’t want any instances of this class, hence the private constructor, which you never call.
  • 4: index = mid; will appear somewhere inside that loop.
  • 5: You can use index < 0 or similar as part of your loop continuation condition
  • 7: You might use a do loop instead of the while loop.
  • [edit]Add /** comment */ to binary search method[/edit]
    Campbell Ritchie
    Sheriff

    Joined: Oct 13, 2005
    Posts: 36575
        
      16
    There is an alternative, that you can put index = -mid - 1; at the end of each iteration of the loop. Then rather than returning -1 for not found, it returns a negative number hinting at the nearest index where you would have found the element sought.
    Luke Stamper
    Ranch Hand

    Joined: Jun 19, 2011
    Posts: 64
    I took a different direction. I am so close to being done. The only thing I have to correct is the testing section L32-45. I am getting this error message.

    Integer test array contains...
    -4 -2 0 2 4 6

    String test array contains...
    Alpha Bravo Charlie Delta Echo Foxtrot 3
    Searcher@1e5e2c3is at index 3 in the array
    Searcher@18a992f is at index 3 in the array




    Is it possible to do something like this in Generics for this program?

    String[] searchFruits = new String[] {"lemon", "apple", "banana", "grapes", "blueberry","papaya"};
    System.out.println("");
    System.out.println("\nChecking fruits...");
    int results;
    for (int key = 0; key < searchFruits.length; key++)
    {
    results = BinarySearchString.searchString(names, searchFruits[key]);

    if (results >= 0) {

    System.out.println(searchFruits[key] + " is at index " + results);
    }
    else {
    System.out.println(searchFruits[key] + " is not in the array.");
    }
    }
    Campbell Ritchie
    Sheriff

    Joined: Oct 13, 2005
    Posts: 36575
        
      16
    Apart from the fact that you ought to say ? super T as I told you yesterday, what else is there?
     
    I agree. Here's the link: http://aspose.com/file-tools
     
    subject: Generic Binary Search for Ints & Strings
     
    Similar Threads
    A Hard Puzzle
    Filling an array?
    NullObject
    recursive binary search : used code may have alternative?
    Binary search in sorted array of strings