Hello Alessandro,
Since the array is sorted already, a good way to solve similar set of problems is popularly known as Binary Search. Binary Search is fastest known technique for similar problems. This runs in a time complexity of O(log(n)) and this also happens to be the fastest known technique.
You can read and learn more about it on Wiki.
As far as implementation is concerned, your implementation involves a recursion which imposes an overhead on the execution time, as well as on the memory requirements. This could be one of the reason for slow execution on large input array.
As a rule of thumb, it is considered a good practice to program in iterative fashion, this helps reduce overhead incurred due to recursive calls.
Following is an implementation of the Binary Search for use case along the lines of yours. This finds out the largest index idx, which satisfies A(idx) <= num. Since it finds out the rightmost idx the case when input array has duplicate elements is taken care of automatically. Also, if it happens that idx == length(A) then it indicates absence of A(idx+1) which is greater than num.
Feel free to customize the following implemenation as per your needs.
function idx = binarySearch(A, num)
l = 1;
r = length(A);
idx = 1;
while l < r
idx = 1 + floor((l + r - 1) / 2);
if A(idx) > num
r = idx - 1;
elseif A(idx) <= num
l = idx;
end
end
if l == r
idx = r;
end
if A(idx) > num
idx = -1;
end
end
Best Answer