How to create binary search code

Question

Camden Nelson 2023-2-12

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1911240-how-to-create-binary-search-code

回答： Raghvi 2023-2-15

I thought I had this code working yesterday but must've changed something on accident. I am not sure how to finish it to perform binary serach. It only says my value isn't present except when in the first index. See code below:

function [out] = BinSearch(x,A)
i = 1; % i is the leftmost index which is 1
j = length(A); % j is the rightmost index which is length(A)
while i < j
    m = 1;
    m = floor((i + j)/2); % Find middle of array
    if x > A(m) % If userval is in the left half of array
        i = m + 1;
    else % Userval is in the right half of array
        j = m;
    end
end
if x == A(i) % If userval is in the first index
    out = i;
else
    out = ('Your number was not found in the array');
end
end

1 个评论
显示 -1更早的评论隐藏 -1更早的评论

Voss 2023-2-12

The function seems like it will work ok when A is non-empty and sorted. Is the A you pass to the function sorted? If you want the function to work for arbitrary A, you can sort A inside the function and also handle the case when A is empty.

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Raghvi 2023-2-15

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1911240-how-to-create-binary-search-code#answer_1171925

在 MATLAB Online 中打开

Hi Camden,

I understand you are having trouble with binary search function. I believe the problem was that you were checking x with first index (i) instead of middle index m. The following code worked for me:

function [out] = BinSearch(x,A)
    i = 1; % i is the leftmost index which is 1
    j = length(A); % j is the rightmost index which is length(A)
    flag = 0;
    while i <= j
        m = ceil((i + j)/2); % Find middle of array
        if A(m)==x
            out = m;
            flag = 1;
            break;
        elseif x > A(m) % If userval is in the left half of array
            i = m + 1;
        else % Userval is in the right half of array
            j = m;
        end
    end
    if flag == 0
        out = ('Your number was not found in the array');
    end
end