Unable to find bug in Problem 56040 which is a Binary Search problem on MATLAB Cody

I'm currently working on an implementation of the binary search algorithm in MATLAB, but I seem to have encountered a bug that I can't quite figure out. I would greatly appreciate your assistance in identifying and resolving the issue.

Here is the code:

function [loc, iter] = binarySearch(X, target)
% Initialize variables
found = false;
iter = 0;
low = 1;
high = numel(X);

while low < high
    mid = floor((low + high) / 2);
    iter = iter + 1;
    
    if X(mid) == target
        found = true;
        break;
    elseif X(mid) < target
        low = mid + 1;
    else
        high = mid - 1;
    end
end

% Check if the target is found
if found
    loc = mid;
else
    loc = -1;  % Target value not found, set loc to -1
end
end

For test case

X = [1, 3, 5, 7, 9];
target = 7;
[loc, iter] = binarySearch(X, target)

The expected output is loc= 4 and iter is 2, while my output is loc = -1 and iter = 4.

Answer 1

[vansh gandhi]

Hello Yash,

I took a look at your code and it seems the bug lies in the termination condition of your while loop (low < high). To fix the problem, you need to change the termination condition to low <= high to ensure the loop terminates correctly when the search range is exhausted.

Here's the corrected version of your code:

function [loc, iter] = binarySearch(X, target)
found = false;
iter = 0;
low = 1;
high = numel(X);

while low <= high
    mid = floor((low + high) / 2);
    iter = iter + 1;
    
    if X(mid) == target
        found = true;
        break;
    elseif X(mid) < target
        low = mid + 1;
    else
        high = mid - 1;
    end
end
if found
    loc = mid;
else
    loc = -1;  % Target value not found, set loc to -1
end
end

I hope this resolves your query.

[Yash Verma]

Can't believe I overlooked this. Thanks for the help.

[Image Analyst]

If this Answer solves your original question, then could you please click the "Accept this answer" link to award the answerer with "reputation points" for their efforts in helping you? They'd appreciate it. Thanks in advance. 🙂 Note: you can only accept one answer (so pick the best one) but you can click the "Vote" icon for as many Answers as you want. Voting for an answer will also award reputation points.

By the way, you should ALWAYS have a failsafe in while loops to prevent and detect infinite loops or loops that exited without ever obtaining the expected termination condition. Here is an example:

% Demonstration of how to avoid an infinite loop by setting up a failsafe.
% Set up a failsafe
maxIterations = 100; % Way more than you think it would ever need.
loopCounter = 0;
% Now loop until we obtain the required condition: a random number equals exactly 0.5.
% If that never happens, the failsafe will kick us out of the loop so we do not get an infinite loop.
r = nan; % Initialize so we can enter the loop the first time.
while (r ~= 0.5) && loopCounter < maxIterations
    loopCounter = loopCounter + 1;
    fprintf('Iteration #%d.\n', loopCounter)
    r = rand;
end
% Alert user if we exited normally, or if the failsafe kicked us out to avoid an infinite loop.
if loopCounter < maxIterations
    % Then the loop found the condition and exited early, which means normally.
    fprintf('Loop exited normally after %d iterations.\n', loopCounter);
else
    % Then the loop never found the condition and exited when the number of iterations
    % hit the maximum number of iterations allowed, which means abnormally.
    fprintf('Loop exited abnormally after iterating the maximimum number of iterations (%d) without obtaining the exit criteria.\n', maxIterations);
end
fprintf('All done after %d iterations.\n', loopCounter)