Ruby Binary Search Code is Not Returning Expected Results

Question

I'm trying to write a binary search method in Ruby and have found a strange situation in which my code doesn't return what I expect it to when I add two numbers together and divide them by two in the elsif statement.

When I give the method a target of 1-3 and an array of [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] then the method works and I get the index of the target I want.

When I give the method a target of 4, I get an infinite loop because the middle = first + last / 2 code is returning 5 rather than the expected 3. I even tried to print a 7/2 result and I got 3, but when it's pulling in the values, it returns 5.

When I give the method a target of 7-10, it breaks and says there's an undefined method '<' for nil:NilClass on line 12 (which is the line that the elsif is on).


def binary_search(target, array)
  middle = array.length / 2
  first = 0
  last = array.length - 1

  while first < last
    if array[middle] == target
      puts "we've found the target! middle is #{middle}"
      return true
    elsif array[middle] < target
      first = middle + 1
      middle = first + last / 2
      puts "we're in the elsif and middle is #{middle}"
    else
      last = middle - 1
      middle = first + last / 2
      puts "we're in the else and middle is now #{middle}"
    end
  end
  false
end

binary_search(4, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10])

user_7190971 · Answer

A prerequisite :

4 + 4 / 2 will give us 6. It's the equivalent of 4 + (4 / 2 ).
(4 + 4) / 2 will give us 4.

The two statements are not equivalent.

On the two middle computation :

middle = first + last / 2

We do not have what we expect.

You are looking to divide first AND last by two. So you will want to have :

middle = (first + last) / 2

If you replace first + last / 2 by (first + last) / 2, your script will give us :

binary_search(4, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
we're in the else and middle is now 2
we're in the elsif and middle is 3
we've found the target! middle is 3
 => true

Ruby Binary Search Code is Not Returning Expected Results

1 Answers