Help with Binary Search+Indices vector using Recursion

11 次查看（过去 30 天）
Cici
Cici 2019-11-21
回答： Sunny Choudhary 2023-6-22
n = 0 ;
indices = [];
function[found_at, indices] = bin_search(data, search, index1, indexn)
mid = floor((indexn+index1)/2);
if search == data(mid)
found_at = mid;
n = n + 1;
indices(n) = mid;
elseif data(mid) > search
indexn = mid - 1;
n = n + 1;
indices(n) = mid;
found_at = bin_search(data, search, index1, indexn);
else
index1 = mid + 1;
n = n + 1;
indices(n) = mid;
found_at = bin_search(data,search,index1, indexn);
endif
end
Above is a recursive function within another main function (I omitted the main because it wasn't important here as it just calls this function).
I need the code to output the index that the 'search' variable was found at into 'found_at' and also output into 'indices' a vector that contains all the indices that the function stopped at until it finds it answer.
For example: if the data was [1 3 4 5 9 12 16] and search = 9, then found_at = 5 and indices = [4 6 5]. But whenever I run this code with the above inputs, my 'found_at' is correct but indices = [4]. What am I doing wrong in my code?
Thank you!

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

回答（1 个）

Sunny Choudhary
Sunny Choudhary 2023-6-22
Ran in:
I have modified your code and we don't need n anymore
All I am doing is
In the base case search == data(mid) just returning mid as indices=[mid] as we have only single elment to return
In the other cases search > data(mid) or search < data(mid) we can update indices as [mid indices] so that mid will get appended before the indices which we got from child call
Here's the code:
data= [1 3 4 5 9 12 16];
search = 9;
indices = [];
[found_at, indices] = bin_search(data,search,1,numel(data));
indices
indices = 1×3
4 6 5
function[found_at, indices] = bin_search(data, search, index1, indexn)
mid = floor((indexn+index1)/2);
if search == data(mid)
found_at = mid;
indices=[mid];
return;
elseif data(mid) > search
indexn = mid - 1;
[found_at,indices] = bin_search(data, search, index1, indexn);
indices=[mid indices];
else
index1 = mid + 1;
[found_at,indices] = bin_search(data,search,index1, indexn);
indices=[mid indices];
end
end

类别

在 Help Center 和 File Exchange 中查找有关 Whos 的更多信息

标签

Community Treasure Hunt

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

Start Hunting!

Translated by