Help with Binary Search+Indices vector using Recursion

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!

Answer 1

[Sunny Choudhary]

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