CODEWITHSUNDEEP
rubyif-statementrecursionbinary-search
Rob Matthews
Rob Matthews

Reputation: 161

manual binary search wrap up

Would anyone be so kind to explain to me how I finish my recursive binary search problem? The recursive aspect is confusing me. I would love for an explanation on what thats doing if possible!!! I think I need to increment the 'half' value I have within the if or elsif but I don't know what it would look like. Please suggest ways to add to the code I currently have rather than refactor to something simpler... at least at first! Thanks!

def binary_search(letter, array)
  half = (array.length - 1)/2
  if letter == array[half]
    return half
  end
  if letter > array[half] && letter <= array[-1]
    array = array[half...array.length]
    binary_search(letter, array)
  elsif letter < array[half] && letter >= array[0]
    array = array[0...half]
    binary_search(letter, array)
  else
    nil
  end
end

arr = [:A, :B, :C, :D, :E, :F, :G]
p binary_search(:C, arr)

Upvotes: 1

Views: 50

Answers (1)

Eric Duminil
Eric Duminil

Reputation: 54223

half was part of the problem. With a length of 2, half would be 0, and you would "split" your array in a full array and an empty array : recursion would never end.

You also need to keep an index, and add half to it when you consider the 2nd Array :

def binary_search(letter, array, i=0)
  puts "Been here for #{array} with #{i}"
  half = array.length / 2
  if letter == array[half]
    return i + half
  end
  if letter > array[half] && letter <= array[-1]
    binary_search(letter, array.drop(half), i + half)
  elsif letter < array[half] && letter >= array[0]
    binary_search(letter, array.take(half), i)
  else
    nil
  end
end

arr = [:A, :B, :C, :D, :E, :F, :G]
p binary_search(:C, arr)
p binary_search(:G, arr)

It outputs 

Been here for [:A, :B, :C, :D, :E, :F, :G] with 0
Been here for [:A, :B, :C] with 0
Been here for [:B, :C] with 1
2
Been here for [:A, :B, :C, :D, :E, :F, :G] with 0
Been here for [:D, :E, :F, :G] with 3
Been here for [:F, :G] with 5
6

Upvotes: 1

Related Questions