COMPGROUPS.NET | Search | Post Question | Groups | Stream | About | Register

### Fastest way of partitioning an array based on a cutoff value

• Follow

```Hi,

What's the fastest way of achieving the following in Matlab. I have a sorted array and a cutoff value. I want to partition the array into two sub arrays a1 and a2, such that a2 contains only the elements that are >=cutoff (one of the two subarrays may end up being empty). I know I can use 'find' or 'logical indexing', but I am  not interested in Matlab searching the entire array (or maybe matlab does that if detects that the array is already sorted, but this will add some overhead)

In other words, what is the fastest way of finding the first element in a sorted array that is greater than or equal a provided value. Once I find that element, I know that any other element before it in the array belongs to the first set, and anything below it belongs to the other set, and there is no need to scan the entire array.

I suspect that some sort of binary search can do the trick, but instead of coding this myself, I was wondering if Matlab has something built in that does this.

Thanks
```
 0

```"Mark" wrote in message <ihljo4\$mc3\$1@fred.mathworks.com>...
> Hi,
>
> What's the fastest way of achieving the following in Matlab. I have a sorted array and a cutoff value. I want to partition the array into two sub arrays a1 and a2, such that a2 contains only the elements that are >=cutoff (one of the two subarrays may end up being empty). I know I can use 'find' or 'logical indexing', but I am  not interested in Matlab searching the entire array (or maybe matlab does that if detects that the array is already sorted, but this will add some overhead)
>
> In other words, what is the fastest way of finding the first element in a sorted array that is greater than or equal a provided value. Once I find that element, I know that any other element before it in the array belongs to the first set, and anything below it belongs to the other set, and there is no need to scan the entire array.
>
> I suspect that some sort of binary search can do the trick, but instead of coding this myself, I was wondering if Matlab has something built in that does this.
>
> Thanks

This one seems fast but I'm sure that's not the fastest one

[row,col]=find(A(:,:)>=value,1,'first');
B=A(row:end,col:end);
```
 0

```Logical indexing (L.I.) is (to my surprise) FASTER than find in the way you proposed (see below)

Maybe 'find' searches linearly while L.I. detects first if the array is sorted? I suppose that it's possible to achieve a faster performance if Matlab does not have to find all the indices unlike L.I. does, but exactly like find (which returns only one index). The question is if there is a built in function that does it. Unfortunately 'find' is slower than L.I., which looks counterintuitive

% Note: change semicolon (;) for comma (,) before toc to see the output of each

>> num_tests = 20;  test_var = cumsum(ones(num_tests, 1)+2)

>> tic, find(test_var < 30, 1, 'last'); toc
Elapsed time is 0.000038 seconds.

>> tic, idices = test_var < 30; toc
Elapsed time is 0.000018 seconds.

"Paulo Silva" wrote in message <ihlmnm\$7i6\$1@fred.mathworks.com>...
> "Mark" wrote in message <ihljo4\$mc3\$1@fred.mathworks.com>...
> > Hi,
> >
> > What's the fastest way of achieving the following in Matlab. I have a sorted array and a cutoff value. I want to partition the array into two sub arrays a1 and a2, such that a2 contains only the elements that are >=cutoff (one of the two subarrays may end up being empty). I know I can use 'find' or 'logical indexing', but I am  not interested in Matlab searching the entire array (or maybe matlab does that if detects that the array is already sorted, but this will add some overhead)
> >
> > In other words, what is the fastest way of finding the first element in a sorted array that is greater than or equal a provided value. Once I find that element, I know that any other element before it in the array belongs to the first set, and anything below it belongs to the other set, and there is no need to scan the entire array.
> >
> > I suspect that some sort of binary search can do the trick, but instead of coding this myself, I was wondering if Matlab has something built in that does this.
> >
> > Thanks
>
> This one seems fast but I'm sure that's not the fastest one
>
> [row,col]=find(A(:,:)>=value,1,'first');
> B=A(row:end,col:end);
```
 0

```"Mark" wrote in message <ihlne7\$mg3\$1@fred.mathworks.com>...
> Logical indexing (L.I.) is (to my surprise) FASTER than find in the way you proposed (see below)
>
> Maybe 'find' searches linearly while L.I. detects first if the array is sorted? I suppose that it's possible to achieve a faster performance if Matlab does not have to find all the indices unlike L.I. does, but exactly like find (which returns only one index). The question is if there is a built in function that does it. Unfortunately 'find' is slower than L.I., which looks counterintuitive

Ah no. The reason FIND is slower than LI is very simple. Before FIND carries out the search, it first builds the array of LOGICAL (test_var < 30). The first step is essentially the what LI does. Thus the time of FIND is always greater than LI. Matlab FIND currently is not smart enough to carry out the logical test on the fly and knows stopping when the first element is encountered.

What you observe has nothing to do about sorting or not.

Bruno
```
 0

```I've been coming across this problem frequently. I've found variants of this solution to work, since it avoids putting the whole array in memory:

cutoff = .3;
A       = sort(rand(10000,1));

Nmin = 0; Nmax = 10000;
while Nmax-Nmin > 1
N = floor(.5*(Nmin+Nmax));
if A(N) > cutoff
Nmax = N;
else
Nmin = N;
end

B1 = A(1:N-1);
B2 = A(N:end);

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <ihlrfj\$ere\$1@fred.mathworks.com>...
> "Mark" wrote in message <ihlne7\$mg3\$1@fred.mathworks.com>...
> > Logical indexing (L.I.) is (to my surprise) FASTER than find in the way you proposed (see below)
> >
> > Maybe 'find' searches linearly while L.I. detects first if the array is sorted? I suppose that it's possible to achieve a faster performance if Matlab does not have to find all the indices unlike L.I. does, but exactly like find (which returns only one index). The question is if there is a built in function that does it. Unfortunately 'find' is slower than L.I., which looks counterintuitive
>
> Ah no. The reason FIND is slower than LI is very simple. Before FIND carries out the search, it first builds the array of LOGICAL (test_var < 30). The first step is essentially the what LI does. Thus the time of FIND is always greater than LI. Matlab FIND currently is not smart enough to carry out the logical test on the fly and knows stopping when the first element is encountered.
>
> What you observe has nothing to do about sorting or not.
>
> Bruno
```
 0
Reply dm17 (1) 12/20/2011 12:16:08 PM

4 Replies
363 Views

Similiar Articles:

7/26/2012 3:36:29 PM