Hi,
I’ve created a binary search using code from wiki and when i run it i
get there error stated below. I’m only using 10 entries so i’m not sure
why it would give me that error. How can I modify my code to handle 100k
entries?
test.rb:14:in binSearch': stack level too deep (SystemStackError) from test.rb:14:inbinSearch’
from test.rb:20
Here is my code:
array = [1, 2, 3, 4, 5, 6, 7, 8, 9 , 10 , 11, 12, 13, 14, 15]
target = 6
left = 0
right = (array.length)
def binSearch(left, right, target, array)
middle = left + ((right - left) / 2)
if array[middle] == target then
puts target
elsif array[middle] > target then
return binSearch(left, middle, target, array)
elsif array[middle] < target then
return binSearch(middle, right, target, array)
else
puts “Target does not exist”
end
end
binSearch(left, right, target, array)
On Aug 7, 7:52 pm, Mrmaster M. [email protected] wrote:
puts target
–
Posted viahttp://www.ruby-forum.com/.
When coding recursively, you always need to test for the exit
condition first. With searches, this means ensuring your result set
isn’t empty before continuing. If your code still loops endlessly
after doing this, it helps to print the search set each step of the
way to see exactly whats going wrong.
(in this case your set is actually the bounds passed to the method,
not the array itself ***)
pharrington wrote:
On Aug 7, 7:52�pm, Mrmaster M. [email protected] wrote:
� � puts target
Posted viahttp://www.ruby-forum.com/.
When coding recursively, you always need to test for the exit
condition first. With searches, this means ensuring your result set
isn’t empty before continuing. If your code still loops endlessly
after doing this, it helps to print the search set each step of the
way to see exactly whats going wrong.
(in this case your set is actually the bounds passed to the method,
not the array itself ***)
When I use 6 it gave me the answer but when I tried 20 as the target i
received that answer. Wouldn’t my exist be the either it found or else
it didn’t?
I’m sorry but i don’t know what you mean by your statement:
(in this case your set is actually the bounds passed to the method,
not the array itself ***)
On Aug 7, 9:04 pm, Mrmaster M. [email protected] wrote:
When I use 6 it gave me the answer but when I tried 20 as the target i
received that answer. Wouldn’t my exist be the either it found or else
it didn’t?
Well, what does “didn’t find it” mean? Think about what a binary
search is: take a bunch of sorted objects, check if what you’re
looking for is in the middle; if not divide that list in two and then
search on the appropriate half. The set gets smaller and smaller (like
little Russian dolls) until either you’ve found the thing or there’s
nothing left. Thus, “didn’t find it” means that there’s nothing left
to search.
I’m sorry but i don’t know what you mean by your statement:
(in this case your set is actually the bounds passed to the method,
not the array itself ***)
–
Posted viahttp://www.ruby-forum.com/.
The… more straight-forward? naive? way to do this is to actually
create another list that’s half of the original list, can search
through that. When doing that, you just check of the list itself is
empty. In this case, you’re changing array bounds to “create” a new
list. So instead of checking if the array is empty, check to see if
nothing can fit within the bounds.
It looks like when the search gets to the right edge, there is nothing
to stop it repeating itself infinitely - which of course blows the
stack. Nothing is noticing that you are only looking at one element and
you did that last time.
Also I question whether right is array.length rather than array.length -
1 since the index starts at 0.
On Fri, Aug 7, 2009 at 6:52 PM, Mrmaster M.
[email protected]wrote:
puts “Target does not exist”
end
end
binSearch(left, right, target, array)
Posted via http://www.ruby-forum.com/.
Hi, you have two issues with your algorithm, that I see. Here is what I
would do http://pastie.org/576485 it explains what the two issues are,
shows
how I would change the code to fix them, as well as a few other small
changes to make the code more usable, then runs through a few tests to
make
sure that it is doing what we think it is doing.
In some browsers, pastie seems to word wrap, so if it does that for you,
you
should probably c&p it into your text editor for reading.
Mike S. wrote:
It looks like when the search gets to the right edge, there is nothing
to stop it repeating itself infinitely - which of course blows the
stack. Nothing is noticing that you are only looking at one element and
you did that last time.
Also I question whether right is array.length rather than array.length -
1 since the index starts at 0.
Thank you all for the clarification on the code. I can’t believe I
missed the exit and forgot about subtracting 1 from length ><.
On Sat, 08 Aug 2009 19:39:35 +0900, Josh C. wrote:
test.rb:14:in `binSearch’: stack level too deep (SystemStackError)
6
elsif array[middle] < target then
Hi, you have two issues with your algorithm, that I see. Here is what I
would do http://pastie.org/576485 it explains what the two issues are,
shows how I would change the code to fix them, as well as a few other
small changes to make the code more usable, then runs through a few
tests to make sure that it is doing what we think it is doing.
In some browsers, pastie seems to word wrap, so if it does that for you,
you should probably c&p it into your text editor for reading.
You can’t write this all in your message so that it can be permenantly
archived wherever the ruby-talk mailing list is mirrored? What happens
if
the pastebin shuts down in the future (e.g. some time next week)? Nobody
will ever know the answer you gave.