Binary search algorithm- find the bit error position
显示 更早的评论
I was trying to implement a binary search algorithm for two random strings. I can able to find the error, but I need to know, which bit position is in error and how to correct it.
X = randi([0,1],10,1);
Y =bsc(X,0.03);
iterate(X,Y)
%%
function res = binaryDivide(list)
n = length(list);
res= {list(1:floor(n/2)), list(floor(n/2)+1:n)};
end
function res = iterate(X,Y)
if length(X)>1
x=binaryDivide(X);
y=binaryDivide(Y);
if sum(x{1})~=sum(y{1})
iterate(x{1},y{1});
elseif sum(x{2})~=sum(y{2})
iterate(x{2},y{2});
end
else
disp([X,Y]);
end
end
1 个评论
Jan
2018-11-20
I've edited the question and applied a code formatting. It is not hard and improves the readability.
采纳的回答
If you want to know the location(s) of the error, you need to keep track of your pivot point (floor(n/2)) and return that together with the list. In iterate you need to add/subtract (depending on which half you're looking at)the pivot location until you find the error bit.
edit: actually there's no subtraction involved. You either add (second half) or do not add (1st half) the pivot location to the current location.
E.g if you call 
the pivot location of step i, if you're comparing [1 1 0 0 0 0 1 1] and [1 1 0 0 0 1 1 1], the location is 
, since at step 0, you're choosing the 2nd half at pivot 
, at the second step, you're choosing the first half at 
and the last step you choose the second half at 
.
the pivot location of step i, if you're comparing [1 1 0 0 0 0 1 1] and [1 1 0 0 0 1 1 1], the location is , since at step 0, you're choosing the 2nd half at pivot , at the second step, you're choosing the first half at and the last step you choose the second half at .更多回答（0 个）
类别
在 帮助中心 和 File Exchange 中查找有关 Creating and Concatenating Matrices 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!
Translated by 
