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

1 次查看（过去 30 天）
Yash Verma
Yash Verma 2023-6-9
评论： Image Analyst 2023-6-9
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.

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

采纳的回答

vansh gandhi
vansh gandhi 2023-6-9
编辑：Image Analyst 2023-6-9
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.
  2 个评论
Image Analyst
Image Analyst 2023-6-9
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)

请先登录，再进行评论。

更多回答（0 个）

类别

在 Help Center 和 File Exchange 中查找有关 Scope Variables and Generate Names 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by