在 matlab 中使用二进制搜索进行插入排序...导致错误"Out of memory. The likely cause is an infinite recursion within the p

Question

我目前正在比较使用线性搜索的插入排序与使用二进制搜索的时间复杂度。while循环A[1…(i-1)]。我一直在matlab中得到错误说明:

unsorted_array =

86    63    36    52    41     8    24    13    19    24

current j: 2电流i: 1低电流:1电流高:1电流中值:1低电流:1电流高:0电流中值:0数组下标必须为正整数或逻辑值。

INSERTION_SORT>BINARY_SEARCH_RECURSIVE出错(第34行)if(key == A(mid))

INSERTION_SORT>BINARY_SEARCH_RECURSIVE出错(第40行)z = BINARY_SEARCH_RECURSIVE(A,key,low,mid-1);

INSERTION_SORT>INSERTION_SORT_BINARY_SEARCH (line . 0)错误51)insertionIndex = BINARY_SEARCH_RECURSIVE(A,key, i);

INSERTION_SORT错误(第5行)sorted_array_using_binary_search =INSERTION_SORT_BINARY_SEARCH (unsorted_array)

我没有看到错误。BINARY_SEARCH_RECURSIVE函数从不返回"low"+ 1"或"低;应该是这样。我再次通过matlab教程，看看我是否在语法上犯了错误。我不明白这个问题，希望能得到一些帮助，找出我到底犯了什么错误。代码如下:

%unsorted_array = randi([1,100],1,10)
unsorted_array = [86    63    36    52    41     8    24    13    19    24]
%sorted_array_using_linear_search = INSERTION_SORT_LINEAR_SEARCH(unsorted_array)
sorted_array_using_binary_search = INSERTION_SORT_BINARY_SEARCH(unsorted_array)

function [y] = INSERTION_SORT_LINEAR_SEARCH(A)
n = length(A);
for j = 2 : n
temp=A(j);
i = j - 1;
while ((i > 0) && (A(i) > temp))
A(i+1) = A(i);
i = i - 1;
end
A(i + 1) = temp;
end
y = A;
end
function [z] = BINARY_SEARCH_RECURSIVE(A,key,low,high)
if(high <= low)
if(key > A(low))
z = (low + 1);
else
z = low;
end
end
disp("current low: " + low)
disp("current high: " + high)
mid = floor((low + high)/2);
disp("current mid: " + mid)
if(key == A(mid))
z = mid+1;
end
if(key > A(mid))
z = BINARY_SEARCH_RECURSIVE(A,key,mid+1,high);
else
z = BINARY_SEARCH_RECURSIVE(A,key,low,mid-1);
end
end
function [x] = INSERTION_SORT_BINARY_SEARCH(A)
n = length(A);
for j = 2 : n
key = A(j);
i = j - 1;
disp("current j: " + j)
disp("current i: " + i)
insertionIndex = BINARY_SEARCH_RECURSIVE(A,key,1,i);
while (i >= insertionIndex)
A(i+1) = A(i);
i = i - 1;
end
A(i+1) = key;
end
x = A
end

Answer 1

烧杯"是对的(在上面的评论中)。我需要设置z =的值(无论索引是low还是low+1)，然后在设置"z"之后放置return。下面的代码可以正常工作:

%unsorted_array = randi([1,100],1,10)
unsorted_array = [86    63    36    52    41     8    24    13    19    24]
sorted_array_using_linear_search = INSERTION_SORT_LINEAR_SEARCH(unsorted_array)
sorted_array_using_binary_search = INSERTION_SORT_BINARY_SEARCH(unsorted_array)

function y = INSERTION_SORT_LINEAR_SEARCH(A)
n = length(A);
for j = 2 : n
temp=A(j);
i = j - 1;
while ((i > 0) && (A(i) > temp))
A(i+1) = A(i);
i = i - 1;
end
A(i + 1) = temp;
end
y = A;
end
function z = BINARY_SEARCH_RECURSIVE(A,key,low,high)
if(high <= low)
disp("first if executed")
if(key > A(low))
disp("second if executed")
z = (low + 1);
return
else
disp("first else executed")
z = low;
return
end
end
disp("current low: " + low)
disp("current high: " + high)
mid = floor((low + high)/2);
disp("current mid: " + mid)
if(key == A(mid))
z = (mid + 1);
end
if(key > A(mid))
z = BINARY_SEARCH_RECURSIVE(A,key,mid+1,high);
else
z = BINARY_SEARCH_RECURSIVE(A,key,low,mid-1);
end
end
function x = INSERTION_SORT_BINARY_SEARCH(A)
n = length(A);
for j = 2 : n
key = A(j);
i = j - 1;
disp("current j: " + j)
disp("current i: " + i)
insertionIndex = BINARY_SEARCH_RECURSIVE(A,key,1,i);
while (i >= insertionIndex)
A(i+1) = A(i);
i = i - 1;
end
A(i+1) = key;
end
x = A
end