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:in `binSearch'
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)
···
--
Posted via http://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 ***)
···
On Aug 7, 7:52 pm, Mrmaster Mrmaster <mrsolarl...@gmail.com> wrote:
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:in `binSearch'
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)
--
Posted viahttp://www.ruby-forum.com/.
Discount Ed hardy tshirt (www.ebuyings.com)
Discount Ed hardy jean (www.ebuyings.com)
Discount Ed hardy shoes (www.ebuyings.com)
Discount Ed hardy handbag (www.ebuyings.com)
Discount Ed hardy other porduct (www.ebuyings.com)
Discount Nike air jordans (www.ebuyings.com)
Discount Nike Air Max 90 Sneakers (www.ebuyings.com)
Discount Nike Air Max 91 Supplier (www.ebuyings.com)
Discount Nike Air Max 95 Shoes Supplier (www.ebuyings.com)
Discount Nike Air Max 97 Trainers (www.ebuyings.com)
Discount Nike Air Max 2003 Wholesale (www.ebuyings.com)
Discount Nike Air Max 2004 Shoes Wholesale
(www.ebuyings.com)
Discount Nike Air Max 2005 Shop (www.ebuyings.com)
Discount Nike Air Max 2006 Shoes Shop (www.ebuyings.com)
Discount Nike Air Max 360 Catalogs (www.ebuyings.com)
Discount Nike Air Max Ltd Shoes Catalogs (www.ebuyings.com)
Discount Nike Air Max Tn Men's Shoes (www.ebuyings.com)
Discount Nike Air Max Tn 2 Women's Shoes (www.ebuyings.com)
Discount Nike Air Max Tn 3 Customize (www.ebuyings.com)
Discount Nike Air Max Tn 4 Shoes Customize
( www.ebuyings.com)
Discount Nike Air Max Tn 6 Supply (www.ebuyings.com)
Discount Nike Shox NZ Shoes Supply (www.ebuyings.com)
Discount Nike Shox OZ Sale (www.ebuyings.com)
Discount Nike Shox TL Store (www.ebuyings.com)
Discount Nike Shox TL 2 Shoes Store (www.ebuyings.com)
Discount Nike Shox TL 3 Distributor (www.ebuyings.com)
Discount Nike Shox Bmw Shoes Distributor (www.ebuyings.com)
Discount Nike Shox Elite Shoes Manufacturer
(www.ebuyings.com)
Discount Nike Shox Monster Manufacturer (www.ebuyings.com)
Discount Nike Shox R4 Running Shoes (www.ebuyings.com)
Discount Nike Shox R5 Mens Shoes (www.ebuyings.com)
Discount Nike Shox Ride Womens Shoes (www.ebuyings.com)
Discount Nike Shox Rival Shoes Wholesaler (www.ebuyings.com)
Discount Nike Shox Energia Wholesaler (www.ebuyings.com)
Discount Nike Shox LV Sneaker (www.ebuyings.com)
Discount Nike Shox Turbo Suppliers (www.ebuyings.com)
Discount Nike Shox Classic Shoes Suppliers
(www.ebuyings.com)
Discount Nike Shox Dendara Trainer (www.ebuyings.com)
Discount Nike Air Jordan 1 Seller (www.ebuyings.com)
Discount Nike Air Jordan 2 Shoes Seller (www.ebuyings.com)
Discount Nike Air Jordan 3 Collection (www.ebuyings.com)
Discount Nike Air Jordan 4 Shoes Collection
(www.ebuyings.com)
Discount Nike Air Jordan 5 Chaussure Shoes
(www.ebuyings.com)
Discount Nike Air Jordan 6 Catalog (www.ebuyings.com)
Discount Nike Air Jordan 7 Shoes Catalog (www.ebuyings.com)
Discount Nike Air Jordan 8 Customized (www.ebuyings.com)
Discount Nike Air Jordan 9 Shoes Customized
(www.ebuyings.com)
Discount Nike Air Jordan 10 Wholesalers (www.ebuyings.com)
Discount Nike Jordan 11 Shoes Wholesalers (www.ebuyings.com)
Discount Nike Air Jordan 12 Factory (www.ebuyings.com)
Discount Nike Air Jordan 13 Shoes Factory (www.ebuyings.com)
Discount Nike Air Jordan 14 Shoes Sell (www.ebuyings.com)
Discount Nike Air Jordan 16 Exporter (www.ebuyings.com)
Discount Nike Air Jordan 17 Shoes Exporter
(www.ebuyings.com)
Discount Nike Air Jordan 18 Offer (www.ebuyings.com)
Discount Nike Air Jordan 19 Shoes Offer (www.ebuyings.com)
Discount Nike Air Jordan 20 Manufacture (www.ebuyings.com)
Discount Nike Jordan 21 Shoes Manufacture (www.ebuyings.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.
···
On Fri, Aug 7, 2009 at 6:52 PM, Mrmaster Mrmaster <mrsolarlife@gmail.com>wrote:
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:in `binSearch'
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)
--
Posted via http://www.ruby-forum.com/\.
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.
···
--
Posted via http://www.ruby-forum.com/.
pharrington 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:
···
On Aug 7, 7:52�pm, Mrmaster Mrmaster <mrsolarl...@gmail.com> wrote:
(in this case your set is actually the bounds passed to the method,
not the array itself ***)
--
Posted via http://www.ruby-forum.com/\.
Mike Stephens 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 ><.
···
--
Posted via http://www.ruby-forum.com/\.
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.
···
On Sat, 08 Aug 2009 19:39:35 +0900, Josh Cheek wrote:
On Fri, Aug 7, 2009 at 6:52 PM, Mrmaster Mrmaster > <mrsolarlife@gmail.com>wrote:
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:in `binSearch'
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) --
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.
--
Chanoch (Ken) Bloom. PhD candidate. Linguistic Cognition Laboratory.
Department of Computer Science. Illinois Institute of Technology.
http://www.iit.edu/~kbloom1/
pharrington wrote:
> 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?
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.
···
On Aug 7, 9:04 pm, Mrmaster Mrmaster <mrsolarl...@gmail.com> wrote: