CODEWITHSUNDEEP
rubybinary-tree
Roarke
Roarke

Reputation: 119

Binary search recursive function not working if target is either the first, or last element in the array

I've been working on this recursive function in Ruby for quite some time now. There's one problem, which I can't seem to fix on my own.

def bsearch(array, target)
    pos = (array.length - 1) / 2
    return pos if array[pos] == target
    if array[pos] < target
        pos += bsearch(array[pos..-1], target)
    else
        pos -= bsearch(array[0..pos], target)
    end
end

The code seems to work as long as the target isn't the first or last element in the array. I can't find the solution to this problem.

Upvotes: 0

Views: 59

Answers (1)

rewritten
rewritten

Reputation: 16435

The line

pos -= bsearch(array[0..pos], target)

should actually be

bsearch(array[0..pos], target)

If you think about it, if your array has length 200, and the item you are looking for is in position 5 of the first half of the array, it is also in position 5 of the wohle array.

Upvotes: 1

Related Questions