Julia在二进制搜索中没有给我一个好的返回值

Question

我在Julia中做了这个递归二进制搜索函数，它将返回我正在寻找的数字的索引。(例如:array = [1,2,4,8,16]， key = 8, output = 4)，但它每次给我的输出都是-1(只有在数字不存在的情况下才应该是这种情况)。下面是代码

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

旁注。二分查找已经在Julia中通过一组searchsorted函数(searchsorted,searchsortedfirst,searchsortedlast)实现了。例如:

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

Answer 2

我认为你只需要改变一下你看它的顺序。

不是

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

你应该改变A[q] > key。你写它是为了在递减数组中找到一个值。您可以通过传递比较器(用于排序)对其进行一般化，然后使用它的值来查找值是应该上升还是下降。如:

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

并使用此值执行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

一个稍微不同的实现，带有注释和更具表现力的名称。你代码中的主要错误是别人指出的elseif A[q] < key。

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

测试:

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