what is "stack level too deep (SystemStackError)" error

[Mrmaster Mrmaster]

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)

 

[pharrington]

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)

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

 

[Mrmaster Mrmaster]

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:

 

[pharrington]

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:

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.

 

[Josh Cheek]

[Note: parts of this message were removed to make it a legal post.]

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)

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

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.

 

[Mrmaster Mrmaster]

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