Binary search algorithm- find the bit error position

2 次查看（过去 30 天）
Rango Depp
Rango Depp 2018-11-20
编辑： Guillaume 2018-11-20
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
Jan 2018-11-20
I've edited the question and applied a code formatting. It is not hard and improves the readability.

请先登录，再进行评论。

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

采纳的回答

Guillaume
Guillaume 2018-11-20
编辑：Guillaume 2018-11-20
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 .

更多回答（0 个）

类别

在 Help Center 和 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