binary insertion

[Mark]

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.

 

[Michael Rauscher]

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

 

[Mark]

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

 

[Michael Rauscher]

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

 

[Wibble]

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.

 

[Michael Rauscher]

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

Sure, but Mark's algorithm does not

Bye
Michael

 

[Mark]

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]

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.

 

[Thomas Weidenfeller]

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

 

[Mark]

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

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]

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

 

[Thomas Weidenfeller]

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

 

[Mark]

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

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.