Julia is not giving me a good return value in Binary Search

Question

I have made this recursive binary search function in Julia that will return the index where the number I am looking for is. (example: array = [1,2,4,8,16], key = 8, output = 4 ), but the output it gives me is -1 every time (that should only be the case if the number does not exist). Here is the code

function binary(A, key)
   return binarystep(A, 1, length(A), key)
end

function binarystep(A, p, r, key)
if p > r
    return -1
else
        q = Int(floor((p+r)/2))
        if A[q] == key
            return q
        elseif A[q] < key
            return binarystep(A, p, q-1, key)
        else 
            return binarystep(A,q+1, r, key)
        end
    end
end

Answer 1

A side note. The binary search is already implemented in Julia through a set of searchsorted functions (searchsorted,searchsortedfirst, searchsortedlast). For an example:

julia> searchsortedfirst([1,2,4,8,16], 4)
3

Answer 2

I think you just need to change the order you are looking at it.

Instead of

elseif A[q] < key
    return binarystep(A, p, q-1, key)
else 
    return binarystep(A,q+1, r, key)
end

You should just change A[q] > key. You wrote it to find a value inside a decreasing array. You could generalize it more by passing it a comparator (used for the sorting) and then use its value for finding if the value should go up or down. Like:

comparator = cpm(A[q], value);

And use this value to do the if:

q = Int(floor((p+r)/2));
comparator = cpm(A[q], value);
if comparator === 0
    return q
elseif comparator < 0
    return binarystep(A, p, q-1, key)
else
    return binarystep(A, q+1, r, key)
end

Answer 3

A slightly different implementation with comments and more expressive names. The main error in your code is elseif A[q] < key as pointed out by others.

binary_search(A, target) = binary_search(A, 1, length(A), target)

function binary_search(A, left, right, target)
    
    left > right && return -1
    
    mid = (left + right) ÷ 2
 
    # Base condition (a target is found)
    if A[mid] == target
        return mid
 
    # discard all elements in the right search space,
    # including the middle element
    elseif A[mid] > target
        binary_search(A, left, mid - 1, target)
 
    # discard all elements in the left search space,
    # including the middle element
    else
        binary_search(A, mid + 1, right, target)
    end 
end

Test:

A = [1, 2, 4, 8, 16]
target = 8
binary_search(A, target)
 4