CODEWITHSUNDEEP
rubyalgorithmsearch
ma22om
ma22om

Reputation: 113

Weird binary search behavior in Ruby

I am trying to implement a recursive binary search in Ruby from scratch.

This is my code:

class Searcher

    def get_limits(array)
        [0, array.length - 1]
    end
    
    def binary_search_recursive(array, key)

        low, high = get_limits(array)
    
        mid = (low + high) / 2
    
        return -1 if low > high
    
        return binary_search_recursive(array[low, mid-1], key) if (array[mid] > key)
    
        return binary_search_recursive(array[mid+1, high], key) if (array[mid] < key)
    
        return mid if (array[mid] == key)
    
    end
    
end     

arr = [1,3,4,12,16,21,34,45,55,76,99,101]
key = 34
s = BinarySearch.new
index = s.binary_search_recursive(arr, key)
puts index

When I put 'key' as 21, it weirdly gives me the right intended answer, the index 5. Arguably, I also get the right answer when 'key' = 3, but I suspect it's by chance.

You see, whenever 'key' != 21 or 3, I get either -1, 0, 1 or 2 for every element of the array. What in the world am I doing wrong?

I've tried several different recursive binary search versions found online, this is just the most recent one. I feel like I get the same issue every time?

Upvotes: 1

Views: 150

Answers (1)

Muhammed Kılı&#231;
Muhammed Kılı&#231;

Reputation: 1279

This is what you ask for after I edited my question. Problem with the code was you were splitting into new array so 34 was the only element at that array at the end therefore index was 0.

class Searcher
    def binary_search(array, val, low=0, high=(length - 1))
        return nil if high < low
        mid = (low + high) >> 1
        case val <=> array[mid]
          when -1
            binary_search(array, val, low, mid - 1)
          when 1
            binary_search(array, val, mid + 1, high)
          else mid
        end
     end
end     

arr = [1,3,4,12,16,21,34,45,55,76,99,101]
key = 34
s = Searcher.new
index = s.binary_search(arr, key, 0, arr.length)
puts index

Upvotes: 1

Related Questions