Fast searching for the lowest value greater than x in a sorted vector
matlab, optimization
Solution
Since the input is already sorted a custom binary search should work (you may need to do some updates for edge cases, i.e value requested is less than all elements of the array):
function [result, res2] = binarySearchExample(val)
%// Generate example data and sort it
N = 100000000;
a = rand(N, 1);
a = sort(a);
%// Run the algorithm
tic % start timing of the binary search algorithm
div = 1;
idx = floor(N/div);
while(1)
div = div * 2;
%// Check if less than val check if the next is greater
if a(idx) <= val,
if a(idx + 1) > val,
result = a(idx + 1);
break
else %// Get bigger
idx = idx + max([floor(N / div), 1]);
end
end
if a(idx) > val, % get smaller
idx = idx - floor(N / div);
end
end % end the while loop
toc % end timing of the binary search algorithm
%% ------------------------
%% compare to MATLAB find
tic % start timing of a matlab find
j = find(a > val, 1);
res2 = a(j);
toc % end timing of a matlab find
%// Benchmark
>> [res1, res2] = binarySearchExample(0.556)
Elapsed time is 0.000093 seconds.
Elapsed time is 0.327183 seconds.
res1 =
0.5560
res2 =
0.5560
Problem
Fast means better than O(N), which is as good as find() is capable of. I know there is `ismembc` and `ismembc2`, but I don't think either of them are what I am looking for. I read the documentation and it seems they search for a member equal to x, but I want the index of first value greater than x. Now if either of these functions is capable of doing this, could somebody please give an example, because I can't figure it out. Ideal behaviour: ``` first_greater_than([0, 3, 3, 4, 7], 1) ``` returns 2, the index of the first value greater than 1, though obviously the input array would be vastly larger. Of course, a binary search isn't too difficult to implement, but if MATLAB has already done it, I would rather use their method.