Ruby Recursive Indexing/Searching Method (Using Middle Comparison) Returning Incorrect Index Value

binary search
ruby array
ruby array index
ruby array slice
ruby hash
ruby array find
ruby search array
binary search python

Self-learning Ruby, on a Recursion unit.

I'm writing a method that will take in two arguments: bsearch(array, target). The array will always be sorted, and I want this method to return the index at which the target is found in this manner using recursion:

Compare the target to the middle element of the (sorted) array. If it is larger than the middle element, then run the method again in the second half of the array. If it is less than the middle element, run the method again with the first half of the array.

I'm having okay results with any target that is less than the middle element, but I'm having issues when the target is greater than the middle element. I can understand the results that come out of these method calls, but I'm unsure how to fix my method in order to get the correct output.

def bsearch(arr, target)
    middle_index = arr.length / 2

    return middle_index if arr[middle_index] == target
    return nil if arr.length == 1

    if target > arr[middle_index]
        bsearch(arr[middle_index+1..-1], target)
    elsif target < arr[middle_index]
        bsearch(arr[0...middle_index], target)
    end
end

When I input:

bsearch([1, 2, 3], 1) # => 0
bsearch([2, 3, 4, 5], 3) # => 1
bsearch([2, 4, 6, 8, 10], 6) # => 2

These all output correctly, but when I run:

bsearch([1, 3, 4, 5, 9], 5) # => 3
bsearch([1, 2, 3, 4, 5, 6], 6) # => 5

They instead return 0 and then 1 respectively. I can see why they do as 0 and 1 are the indices of the target in the smaller, newer version of the arr: [5,9] (5 is at index 0) and then [5,6] (6 is at index 1).

How am I able access the correct middle_index for these two cases?

Any comments and reasoning on how to improve/streamline my method would be helpful as I'm still learning as well!

Every time you recurse into the right half of the search array, your start index relative to the original array gets offset by middle_index + 1. So, just add that offset to the result! You only need to change a single line in your method:

bsearch(arr[middle_index+1..-1], target)

becomes

bsearch(arr[middle_index+1..-1], target) + middle_index + 1
#                                       ↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑

Note! Your original method was tail-recursive. This one is not, since the tail call is to + and not to bsearch. [Ruby does not optimize tail recursion or tail calls, so it doesn't matter, but e.g. Scala optimizes tail recursion and ECMAScript even optimizes all tail calls, so in those languages, I have now turned a perfectly safe method using O(1) memory into a method that uses O(log n) memory.]

This is because we have to keep our state somewhere, and when we program recursively, we usually keep our state on the stack. (This style of recursive programming is typical for purely functional languages which do not have mutable data structures, and so the stack is the only place where you can store state.)

In this case, I have stored the state as a stack of method calls to + that are executed after the actual search has finished. However, there are two things that are stored on the stack: instruction pointers and arguments.

So, a standard way of turning a non tail-recursive method into a tail-recursive one is to move the value that we accumulate using method calls into an argument and pass it to each subsequent recursive call.

This requires us to modify the signature of the method and add an additional parameter:

def bsearch(arr, target, offset)
#                      ↑↑↑↑↑↑↑↑
  middle_index = arr.length / 2

  return middle_index if arr[middle_index] == target
  return nil if arr.length == 1

  if target > arr[middle_index]
    bsearch(arr[middle_index+1..-1], target, offset)
    #                                      ↑↑↑↑↑↑↑↑
  elsif target < arr[middle_index]
    bsearch(arr[0...middle_index], target, offset)
    #                                    ↑↑↑↑↑↑↑↑
  end
end

bsearch([1, 3, 4, 5, 9], 5, nil)

At the moment, we haven't actually done anything, just added a new parameter to the method definition, and then of course we also need to add an argument to every method call. But we are not doing anything with that yet. We need to actually do anything with that parameter. We do more or less the same thing we did before:

def bsearch(arr, target, offset)
  middle_index = arr.length / 2

  return offset + middle_index if arr[middle_index] == target
  #      ↑↑↑↑↑↑↑↑↑
  return nil if arr.length == 1

  if target > arr[middle_index]
    bsearch(arr[middle_index+1..-1], target, offset + middle_index + 1)
    #                                              ↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑
  elsif target < arr[middle_index]
    bsearch(arr[0...middle_index], target, offset)
  end
end

bsearch([1, 3, 4, 5, 9], 5, 0)
#                           ↑

We need to make sure that we "modify" (i.e. pass the new value) the argument when we recurse into the right half of the search array, we need to make sure that we actually add the accumulated value when we have finally found the value, and we need to make sure that we initialize it with the correct value.

This is a bit ugly, though, since we modified the signature of our method, and now the caller needs to make sure to always pass 0 as the last argument. This is bad API design.

We can fix that, by making offset an optional positional parameter with a default argument value of 0:

def bsearch(arr, target, offset=0)
#                              ↑↑

Then, we no longer need to pass the 0 at the call site. But, this is still ugly, since it still modifies the signature, and for example someone could accidentally pass 42. Basically, we are now leaking a private internal implementation detail, namely our accumulator value for making our method tail-recursive, to the outside. Nobody cares whether we implemented our method using tail-recursion, or a loop, or by sending carrier pigeons to China and having child slaves in a sweat shop find the number by hand. (Well, that would be illegal, immoral, and awful, but it should not be part of our method signature.)

Most languages that support proper tail calls or proper tail recursion, also support nested or local subroutines, so the standard pattern for hiding an implementation detail like this is to have a wrapper method that does nothing but call a nested method that does the actual work. Often, this method is named after the outer method with a suffix, i.e. in Haskell, it is common to have the helper function for foo named foo' ("foo prime"), in Scala, it is fooRec. Sometimes, it is simply called go or doit.

E.g. in Scala, we would define our method like this:

def bsearch[A : Ordering](arr: IndexedSeq[A])(target: A) = {
  def bsearchRec(arr: IndexedSeq[A], target: A, accumulator: Long = 0) = {
    ??? // the code
  }

  bsearchRec(arr, target)
}

or in ECMAScript like this:

function bsearch(arr, target) {
  function bsearchRec(arr, target, accumulator = 0) {
    // the code
  }

  return bsearchRec(arr, target);
}

Ruby unfortunately does not have nested subroutines like this. Our alternatives are private methods and lambdas:

def bsearch(arr, target) bsearch_rec(arr, target) end

private def bsearch_rec(arr, target, offset=0)
  middle_index = arr.length / 2

  return offset + middle_index if arr[middle_index] == target
  return nil if arr.length == 1

  if target > arr[middle_index]
    bsearch_rec(arr[middle_index+1..-1], target, offset + middle_index + 1)
  elsif target < arr[middle_index]
    bsearch_rec(arr[0...middle_index], target, offset)
  end
end

bsearch([1, 3, 4, 5, 9], 5)

Or

def bsearch(arr, target)
  bsearch_rec = nil

  bsearch_rec = ->(arr, target, offset=0) {
    middle_index = arr.length / 2

    return offset + middle_index if arr[middle_index] == target
    return nil if arr.length == 1

    if target > arr[middle_index]
      bsearch_rec.(arr[middle_index+1..-1], target, offset + middle_index + 1)
    elsif target < arr[middle_index]
      bsearch_rec.(arr[0...middle_index], target, offset)
    end
  }

  bsearch_rec.(arr, target)
end

bsearch([1, 3, 4, 5, 9], 5)

This will create a new lambda at every call, though, so we can pull that lambda out of the method into a local variable, but then we need to turn the method itself into a block, so it can close over that variable:

bsearch_rec = nil

bsearch_rec = ->(arr, target, offset=0) {
  middle_index = arr.length / 2

  return offset + middle_index if arr[middle_index] == target
  return nil if arr.length == 1

  if target > arr[middle_index]
    bsearch_rec.(arr[middle_index+1..-1], target, offset + middle_index + 1)
  elsif target < arr[middle_index]
    bsearch_rec.(arr[0...middle_index], target, offset)
  end
}

define_method(:bsearch) {|arr, target|
  bsearch_rec.(arr, target)
}

bsearch([1, 3, 4, 5, 9], 5)

Class: Array (Ruby 2.6), Array. Arrays are ordered, integer-indexed collections of any object. The method pop removes the last element in an array and returns it: A useful method if you need to remove nil values from an array is compact: Searches through an array whose elements are also arrays comparing obj with the first element of each� Teams. Q&A for Work. Stack Overflow for Teams is a private, secure spot for you and your coworkers to find and share information.

You could write the recursion as follows.

def bsearch(arr, target)
  return nil if target < arr.first || target > arr.last
  recurse(arr, target, 0, arr.size-1)
end

def recurse(arr, target, low, high)
  mid = (low+high)/2
  case target <=> arr[mid]
  when 0
    mid
  when -1
    recurse(arr, target, low, mid-1) unless low==mid
  when 1
    recurse(arr, target, mid+1, high) unless high==mid
  end
end

arr = [1, 2, 3, 5, 6]
bsearch(arr, 5) #=> 3 
bsearch arr, 1) #=> 0 
bsearch arr, 4) #=> nil 
bsearch arr, 0) #=> nil 

Complex recursive methods can be difficult to debug. One can insert puts statements, but the results may be confusing because it is not clear which nested instance of the method is being called. Here is a technique, applied to this problem, that can be helpful in those debugging efforts.

INDENT = 4

def indent
  @offset += INDENT
  puts
end

def undent
  @offset -= INDENT
  puts
end

def pu(str)
  puts ' '*@offset + str
end

def bsearch(arr, target)
  @offset = 0
  pu "passed to bsearch: arr=#{arr}, target=#{target}"
  puts
  return nil if target < arr.first || target > arr.last
  recurse(arr, target, 0, arr.size-1)
end

def recurse(arr, target, low, high)
  pu "passed to recurse: low=#{low}, high=#{high}"
  mid = (low+high)/2
  pu "mid=#{mid}"
  case target <=> arr[mid]
  when 0
    pu "target==arr[mid] so return mid=#{mid}"
    rv = mid
  when -1
    pu "target < arr[mid]"
    if low==mid
      rv = nil
      pu "low==mid so return nil"
    else
      pu "calling recurse(arr, target, #{low}, #{mid-1})"
      indent   
      rv = recurse(arr, target, low, mid-1)
      pu "recurse(arr, target, #{low}, #{mid-1}) returned #{rv}"
    end
  when 1
    pu "target > arr[mid]"
    if high==mid
      rv = nil
      pu "high==mid so return nil"
    else
      pu "calling recurse(arr, target, #{mid+1}, #{high})"
      indent   
      rv = recurse(arr, target, mid+1, high)
      pu "recurse(arr, target, #{mid+1}, #{high}) returned #{rv}"
    end
  end
  pu "returning #{rv.nil? ? "nil" : rv}"
  undent
  rv
end

bsearch [1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13], 2 

prints the following.

passed to bsearch: arr=[1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13]
                   target=2

passed to recurse: low=0, high=11
mid=5
target < arr[mid]
calling recurse(arr, target, 0, 4)

    passed to recurse: low=0, high=4
    mid=2
    target < arr[mid]
    calling recurse(arr, target, 0, 1)

        passed to recurse: low=0, high=1
        mid=0
        target > arr[mid]
        calling recurse(arr, target, 1, 1)

            passed to recurse: low=1, high=1
            mid=1
            target==arr[mid] so return mid=1
            returning 1

        recurse(arr, target, 1, 1) returned 1
        returning 1

    recurse(arr, target, 0, 1) returned 1
    returning 1

recurse(arr, target, 0, 4) returned 1
returning 1

Binary search, A binary search divides a range of values into halves, and continues to return the index of some element that equals the given value (if there are Recursive Pseudocode: This algorithm only requires one comparison per level. Indexing an array with a negative number could produce an Ruby[edit]. Note also that I haven't said anything at all about nested functions that are not used for currying, as in this case, for example [Code adapted from Ruby Recursive Indexing/Searching Method (Using Middle Comparison) Returning Incorrect Index Value]:

Understanding that the goal here is to use recursion, I'd suggest going about it the following way.

You'll want to track the low_index and high_index (number of elements) through the recursion so that each time the method is called you are looking for the value between an index range rather than a subset of the original list.

# Array, Target, first index (0), number of elements in the array
def bsearch(arr, target, low, high)
    middle_index = (low + high) / 2

    if target > arr[middle_index]
        bsearch(arr, target, middle_index, high)
    elsif target < arr[middle_index]
        bsearch(arr, target, low, middle_index)
    elsif arr[middle_index] == target
      middle_index
    end
end


puts bsearch([1, 2, 3], 1, 0, 3)
#=> 0

puts bsearch([2, 3, 4, 5], 3, 0, 4)
#=> 1

puts bsearch([2, 4, 6, 8, 10], 6, 0, 5)
#=> 2

puts bsearch([1, 3, 4, 5, 9], 5, 0, 5)
#=> 3

puts bsearch([1, 2, 3, 4, 5, 6], 6, 0, 6)
#=> 5

This doesn't take into consideration if an element does NOT exist in the list, however, it's a solution for the recursion path.

Are you one of the 10% of programmers who can write a binary , The range is shrunk by comparing its middle element to T and the above description in hand, writing the code is easy; they're wrong. familiar with the binary search algorithm, but for those of you who are not, the possibility of numeric overflow in index calculations can be ignored. if a[mid] < value. An icon used to represent a menu that can be toggled by interacting with this icon.

class Array - Documentation for Ruby 2.0.0, Arrays are ordered, integer-indexed collections of any object. A useful method if you need to remove nil values from an array is compact: is created by passing the element's index to the given block and storing the return value. Searches through an array whose elements are also arrays comparing obj with the first� Search the history of over 446 billion web pages on the Internet.

Interpolation Search, Given a sorted array of n uniformly distributed values arr[], write a function to Binary Search always goes to the middle element to check. be searched lo ==> Starting index in arr[] hi ==> Ending index in arr[]. Algorithm return -1;. } // Probing the position with keeping. // uniform distribution in mind. Recursive Solution :. By itself, this minimal P, whose unmarked feature value as a sister to V is +DIR, is semantically inert. However, the “case feature” assigned by P to the indirect object NP is actually the unmarked value of P itself, here +DIR. As a case feature on NP, +DIR contributes to interpretation.

Why start + (end, I am very sure that everyone is able to find middle index of array once you know start index and The very first way of finding middle index is mid = (start + end)/2 . But there is problem with this approach, what if value of start or end or both is INT_MAX, it will printf ( "mid using start + (end - start)/2 = %dn" , mid2);. return 0 ;. Ruby Recursive Indexing/Searching Method (Using Middle Comparison) Returning Incorrect Index Value Hot Network Questions Advantages of launching very large rocket while submerged, buoyant, in a body of water

Binary search algorithm, Algorithm[edit]. Binary search works on sorted arrays. Binary search begins by comparing an element in the middle of the array with the target value. If� Returning the response. Finally, you can send to the user the response he is waiting for. Depending on the service you are using, it might be either responding to the request you received or a new call to make. The second options is more flexible as it will allow you to send back more than one message for example. Conclusion

Comments
  • I believe you want arr.each_index.find { |i| arr[i] == target }.
  • Hint 1: how many items do you remove at the beginning of the array? Hint 2: how do you make a number larger by a certain amount?
  • Hi Cary, thanks for the help! We were asked to do this with recursion using this specific type of algorithm however.
  • Jörg, thanks for taking the effort to lead me up to the answer on my own.
  • Still don't quite get it though.. Do I need a counter variable or something to keep track of my real index?
  • This breaks the api, but otherwise yes, this works. Produces fewer temp arrays too :)
  • That's true about no temp arrays. What API are you referring to?
  • Is there anyway to do this while keeping the arguments the same? For example not creating new arguments for the methods, and just doing it with the array and target?
  • Are you allowed to create variables outside the method?
  • @SebastianScholl: signature of bsearch. Easily fixable by having default values for the indexes parameters