binary insertion

Discussion in 'Java' started by Mark, Sep 26, 2006.

  1. Mark

    Mark Guest

    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]) > 0) i++;
    return i;

    but it's slower.
     
    Mark, Sep 26, 2006
    #1
    1. Advertising

  2. Mark schrieb:
    > 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;
    > }
    > }



    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
     
    Michael Rauscher, Sep 26, 2006
    #2
    1. Advertising

  3. Mark

    Mark Guest

    Michael Rauscher wrote:
    > Mark schrieb:
    > > 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;
    > > }
    > > }

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


    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]
    [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 :)
     
    Mark, Sep 26, 2006
    #3
  4. 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
    > 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.


    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
     
    Michael Rauscher, Sep 26, 2006
    #4
  5. Mark

    Wibble Guest

    Michael Rauscher wrote:
    > 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
    >> 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.

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

    Actually, java.util.Arrays.binarySearch does return the insertion point.
     
    Wibble, Sep 26, 2006
    #5
  6. Wibble schrieb:
    > Actually, java.util.Arrays.binarySearch does return the insertion point.


    Sure, but Mark's algorithm does not :)

    Bye
    Michael
     
    Michael Rauscher, Sep 26, 2006
    #6
  7. Mark

    Mark Guest

    Wibble wrote:
    > Michael Rauscher wrote:
    > > 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
    > >> 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.

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

    > Actually, java.util.Arrays.binarySearch does return the insertion point.


    my goodness...I wish I knew this existed before.
     
    Mark, Sep 28, 2006
    #7
  8. Mark

    Mark Guest

    Michael Rauscher wrote:
    > 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
    > > 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.

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


    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.
     
    Mark, Sep 28, 2006
    #8
  9. Mark wrote:
    > Wibble wrote:
    >> 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
    --
    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
     
    Thomas Weidenfeller, Sep 28, 2006
    #9
  10. Mark

    Mark Guest

    Thomas Weidenfeller wrote:
    > Mark wrote:
    > > Wibble wrote:
    > >> 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
    > --
    > 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


    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.
     
    Mark, Sep 28, 2006
    #10
  11. Mark wrote:
    > 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) "

    --
    John W. Kennedy
    "The blind rulers of Logres
    Nourished the land on a fallacy of rational virtue."
    -- Charles Williams. "Taliessin through Logres: Prelude"
     
    John W. Kennedy, Sep 29, 2006
    #11
  12. Mark wrote:
    > Thomas Weidenfeller wrote:
    >> 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.

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


    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
    --
    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
     
    Thomas Weidenfeller, Sep 29, 2006
    #12
  13. Mark

    Mark Guest

    John W. Kennedy wrote:
    > Mark wrote:
    > > 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) "
    >
    > --
    > John W. Kennedy
    > "The blind rulers of Logres
    > 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.
     
    Mark, Oct 5, 2006
    #13
  14. Mark

    Mark Guest

    Thomas Weidenfeller wrote:

    > 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, Oct 5, 2006
    #14
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Fangs
    Replies:
    3
    Views:
    9,949
    darshana
    Oct 26, 2008
  2. N.
    Replies:
    3
    Views:
    8,801
    charles8784
    Sep 22, 2007
  3. Indrajeet

    Basic question in binary tree node insertion

    Indrajeet, Oct 11, 2009, in forum: C Programming
    Replies:
    2
    Views:
    739
    Eric Sosman
    Oct 11, 2009
  4. Julia Jacobson
    Replies:
    7
    Views:
    1,669
    Peter Otten
    Aug 23, 2010
  5. Replies:
    0
    Views:
    1,090
Loading...

Share This Page