Home | Contact Us | FAQ | Search & Site Map | Link to Us
Sign In | Join | Other 45 Sites in Network
HomeAnnouncementsWhite Papers
Discussion GroupsFirst AidDatabasesJavaBeansGUIJava 3DVirtual MachineCORBASecurityToolsGeneral
Java DirectoryOpen Source ProjectsSample Book ChaptersUser GroupsWeb Resources
Related Topics
Databases.NETMore Topics ...

Java Forum / General / October 2006

Tip: Looking for answers? Try searching our database.

binary insertion

Thread view: 
Mark - 26 Sep 2006 03:14 GMT
i can't seem to get my binary insert to work properly.

any help would be appreciated.

this function should return the location where newBook should be
inserted.. for example, if i have an array {AA,AB,AC,AE} and i want to
insert AD, it should return 3 (the index of AE).  AE is then bumped
over by my other function..which works fine, i tested it with a simple
linear  algorithm.

    private int findInsertLocation(Resource newBook, int index)
    {
        int low = 0, high = size[index]-1;

        while( low < high )
        {
            int mid = (low+high)/2;

            if( newBook.compareTo(book[index][mid]) >= 0 )
                low = mid + 1;
            else
                high = mid;
        }
    }

and you might want these...

    public String toStringForCompare() {
        return lastName + firstName + title + editionNumber;
    }

    // comparisons
    public int compareTo(Resource anotherBook) {
        return
toStringForCompare().compareToIgnoreCase(anotherBook.toStringForCompare());
    }

this however works fine..

        int i=0;
        while(i<size[index]&&newBook.compareTo(book[index][i]) > 0) i++;
        return i;

but it's slower.
Michael Rauscher - 26 Sep 2006 05:23 GMT
Mark schrieb:
> i can't seem to get my binary insert to work properly.
>
[quoted text clipped - 20 lines]
>         }
>     }

1. Your method doesn't return a value.

2. You don't need a size array (high = book[index].length - 1)

3. You wouldn't have to rely on the book-array if you changed
   the signature of the method to

   int findInsertLocation( Resource newBook, Resource[] books )

4. Imagine your array as tree, then the binary search algorithm
   would return a leaf (a node in the tree with no children).
   To get the insertion point you'd have to compare the leaf to
   the element you searched for.

Bye
Michael
Mark - 26 Sep 2006 08:04 GMT
> Mark schrieb:
> > i can't seem to get my binary insert to work properly.
[quoted text clipped - 38 lines]
> Bye
> Michael

1.  errr... I must have deleted the return statement.  I was madly
trying to edit it, but then got frusterated and implemented a simpler
solution.  you see, my assignment is due in about 60 seconds.. but .. I
guess my prof was generous and gave us a 15 minute extension.

2.  anyways... a very much do need a size array because the arrays are
not full.

3.  well..it needs to return an index so that I can shift all the
elements to the right of that index over one to make room for the new
element

4.  a tree? I think perhaps you misinterpreted what I have here.. it's
more like

[*][book1][book2][book3][book4]
[a]
[b][book5]
[c]
.
.
.
[z][book6][book7]

where the first index acts as..well..an index. first letter of the
author's last name for super-quick access.

I guess I should have posted a few more details. sorry :)
Michael Rauscher - 26 Sep 2006 11:48 GMT
Mark schrieb:

> 1.  errr... I must have deleted the return statement.  I was madly
> trying to edit it, but then got frusterated and implemented a simpler
[quoted text clipped - 3 lines]
> 2.  anyways... a very much do need a size array because the arrays are
> not full.

good point.

> 3.  well..it needs to return an index so that I can shift all the
> elements to the right of that index over one to make room for the new
> element
>
> 4.  a tree? I think perhaps you misinterpreted what I have here.. it's
> more like

I didn't misinterprete your post. Perhaps I was just unable to express
myself well.

Let's take one of these arrays:

[book1 book2 book3 book4]

If you can perform a binary search on that array, it's ordered.
Therefore you can imagine a decision tree, e. g.

          [book1 book2 book3 book4]
                     /\
                    /  \
                   /    \
        [book1 book2] [book3 book4]
              /\            /\
             /  \          /  \
         book1 book2   book3 book4

The binary search algorithm will return a leaf of that tree so it should
get clear, that you've got to decide if the leaf is smaller or equal to
or greater than the element you searched for.

In other words: the algorithm will return the index of an element of the
array but not the insertion point.

Bye
Michael
Wibble - 26 Sep 2006 12:34 GMT
> Mark schrieb:
>>
[quoted text clipped - 43 lines]
> Bye
> Michael
Actually, java.util.Arrays.binarySearch does return the insertion point.
Michael Rauscher - 26 Sep 2006 13:42 GMT
Wibble schrieb:
> Actually, java.util.Arrays.binarySearch does return the insertion point.

Sure, but Mark's algorithm does not :)

Bye
Michael
Mark - 28 Sep 2006 05:48 GMT
> > Mark schrieb:
> >>
[quoted text clipped - 44 lines]
> > Michael
> Actually, java.util.Arrays.binarySearch does return the insertion point.

my goodness...I wish I knew this existed before.
Thomas Weidenfeller - 28 Sep 2006 09:25 GMT
>> Actually, java.util.Arrays.binarySearch does return the insertion point.
>
> my goodness...I wish I knew this existed before.

That's why we try so hard to convince people to read and search the
documentation. Its not there for pure decorative purposes. One can gain
something from looking at it. Really.

/Thomas
Signature

The comp.lang.java.gui FAQ:
http://gd.tuwien.ac.at/faqs/faqs-hierarchy/comp/comp.lang.java.gui/
ftp://ftp.cs.uu.nl/pub/NEWS.ANSWERS/computer-lang/java/gui/faq

Mark - 28 Sep 2006 18:59 GMT
> >> Actually, java.util.Arrays.binarySearch does return the insertion point.
> >
[quoted text clipped - 9 lines]
> http://gd.tuwien.ac.at/faqs/faqs-hierarchy/comp/comp.lang.java.gui/
> ftp://ftp.cs.uu.nl/pub/NEWS.ANSWERS/computer-lang/java/gui/faq

my bad. i usually do google up functions, but for some reason i didn't
think to check for something like that.

but i must say.. java sun's documentation really sucks.
if you look up compareTo for strings, it doesnt even tell you what
-1,0, and 1 actually mean...even if it is somewhat intuitivly obvious.
that and they don't provide any examples...

now compare that with php.net's stuff..100x better. and anything that
*isnt* in the documentation is usually posted by some nice feller just
below.

but that's my little rant.
John W. Kennedy - 29 Sep 2006 03:52 GMT
 > but i must say.. java sun's documentation really sucks.
> if you look up compareTo for strings, it doesnt even tell you what
> -1,0, and 1 actually mean...even if it is somewhat intuitivly obvious.

¿Que?

"The result is a negative integer if this String object
lexicographically precedes the argument string. The result is a positive
integer if this String object lexicographically follows the argument
string. The result is zero if the strings are equal; compareTo returns 0
exactly when the equals(Object) method would return true.

"This is the definition of lexicographic ordering. If two strings are
different, then either they have different characters at some index that
is a valid index for both strings, or their lengths are different, or
both. If they have different characters at one or more index positions,
let k be the smallest such index; then the string whose character at
position k has the smaller value, as determined by using the < operator,
lexicographically precedes the other string. In this case, compareTo
returns the difference of the two character values at position k in the
two string -- that is, the value:

     this.charAt(k)-anotherString.charAt(k) "

Signature

John W. Kennedy
"The blind rulers of Logres
Nourished the land on a fallacy of rational virtue."
  -- Charles Williams.  "Taliessin through Logres: Prelude"

Mark - 05 Oct 2006 22:29 GMT
>   > but i must say.. java sun's documentation really sucks.
> > if you look up compareTo for strings, it doesnt even tell you what
[quoted text clipped - 25 lines]
> Nourished the land on a fallacy of rational virtue."
>    -- Charles Williams.  "Taliessin through Logres: Prelude"

>.<
I don't know what i was looking at when I wrote that.
I don't think I've been getting enough sleep.
Thomas Weidenfeller - 29 Sep 2006 08:05 GMT
>> That's why we try so hard to convince people to read and search the
>> documentation. Its not there for pure decorative purposes. One can gain
[quoted text clipped - 3 lines]
> -1,0, and 1 actually mean...even if it is somewhat intuitivly obvious.
> that and they don't provide any examples...

Bzzzz. Game Over on Player One - You lost.

You are just demonstrating that you haven't read the documentation. It
is explained in detail right in the String.compareTo() method's API
documentation.

> now compare that with php.net's stuff..100x better.

Sure, if you like your daily does of yet another PHP vulnerably use PHP.

/Thomas
Signature

The comp.lang.java.gui FAQ:
http://gd.tuwien.ac.at/faqs/faqs-hierarchy/comp/comp.lang.java.gui/
ftp://ftp.cs.uu.nl/pub/NEWS.ANSWERS/computer-lang/java/gui/faq

Mark - 05 Oct 2006 22:32 GMT
> Sure, if you like your daily does of yet another PHP vulnerably use PHP.
>
> /Thomas

Vulnerability? I'll cry when I get hacked, but at the moment my site is
too small for anyone to care enough to try.  It serves my purposes, I'm
content.
I'm not even going to say you're wrong, because really I have no idea,
I'll admit that.
Mark - 28 Sep 2006 05:52 GMT
> Mark schrieb:
> >
[quoted text clipped - 43 lines]
> Bye
> Michael

well..okay. fair enough, i suppose that is one way of representing it,
although i don't really think it helps me get a clearer picture of what
i was trying to do. i still prefer to think of it using the box model..
and then just chopping it in half, and half, and half...

oh well. it's too late now. i'm sure i would have been able to figure
something out if i thought about it just a bit longer.

i mean..it was returning results *close* to what i wanted..but it was
usually off by about 1 index.


Free Magazines

Get these publications absolutely FREE for up to 12 months. There are no hidden fees and no obligation. Simply choose a title, complete the application form and submit it. Read more ...

Oracle MagazineNetwork ComputingComputer WorldBio-IT WorldeWeekInformation WeekInfosecurity
 
Sign In
Join
My Latest Posts
My Monitored Threads
My Blog
My Photo Gallery
My Profile
My Homepage

Start New Thread
Enable EMail Alerts
Rate this Thread



©2008 Advenet LLC   Privacy Policy - Terms of Use
This website includes both content owned or controlled by Advenet as well as content owned or controlled by third parties.