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

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