# Is there a way to obtain desired index without using 'find'?

87 views (last 30 days)

Show older comments

Dear all,

Suppose there is some array

ar=[102 243 453 768 897 ...]

Is there any way to obtain indices of an element having value e.g. 243 without using find?

For each element I need to find its index, so the computational cost will be O(N^2), which is too much. One possibility is using sparse matrices, e.g.

smatr=sparse(ar,1,1:length(ar))

and then index can be retrieved simply as ind=smatr(243) and so on, reducing computational cost to O(N). However, the problem is that in my computations values of 'ar' might exceed maximum size of matrix. So is there any additional way to relate values of 'ar' to indices so the latter can be obtained in one operation?

Thanks,

Dima

##### 9 Comments

### Accepted Answer

Matt J
on 2 Oct 2012

Edited: Matt J
on 2 Oct 2012

Here's another approach that uses the find_idx function from the FEX

It seems to overcome the O(N) overhead of HISTC and is virtually independent of N in speed,

ar=[102 243 453 768 897 102];

[sar,i,j]=unique(ar);

ind=j(floor(find_idx(768,sar))), %search for 768 for example

### More Answers (7)

Matt Fig
on 1 Oct 2012

ar=[102 243 453 768 897 243 653 23];

KEY = 1:length(ar);

KEY(ar==243)

##### 2 Comments

Matt J
on 1 Oct 2012

Edited: Matt J
on 1 Oct 2012

Here's a modification of the sparse matrix approach that might ease the difficulty with maximum matrix sizes limits,

armax=max(ar);

armin=min(ar);

arc=ar-armin+1;

arcmax=armax-armin+1;

N=ceil(sqrt(arcmax));

[I,J]=ind2sub([N,N], arc);

smatr=sparse(I,J,1:length(arc),N,N);

Now, whenever you need to look up an index, e.g. 243, you would do

[i,j]=ind2sub([N,N],243-armin+1);

ind=smatr(i,j);

The difference is that now the matrix dimensions of smatr are roughly the square root of what they were in your approach. Even less, actually, since we offset the ar values by armin in its construction.

##### 2 Comments

Walter Roberson
on 1 Oct 2012

Matt J
on 1 Oct 2012

Edited: Matt J
on 1 Oct 2012

Here is an implementation of your O(log_2(N)) idea using HISTC

ar=[102 243 453 768 897 102];

[sar,i,j]=unique(ar);

[~,bin]=histc(768,sar); %search for 768 for example

ind=j(bin);

Walter Roberson
on 1 Oct 2012

If each element is present only once, consider using the three-output form of unique()

##### 5 Comments

dipanka tanu sarmah
on 19 Oct 2017

Edited: Walter Roberson
on 19 Oct 2017

you can use the following function :

function posX = findPosition(x,y)

posX=[];

for i =1:length(x)

p=x-y;

isequal(p(i),0)

if ans==1

posX=[posX,i]

end

end

##### 2 Comments

dipanka tanu sarmah
on 19 Oct 2017

yeah. u are awesome. I didnt go thriugh the optimization part. thnk you

Walter Roberson
on 19 Oct 2017

myMap = containers.Map( ar, 1:length(ar) )

This uses a hash structure. I am not sure which one it uses, so I do not know the creation time costs; certainly no less than O(N) as the 1:length(ar) is O(N). O(N*log(N)) I suspect.

Once hashed, each lookup is nominally constant time (I do not know if the hash structure it uses can have collisions that might need to be resolved.)

##### 0 Comments

Christian Troiani
on 12 Nov 2017

Edited: Walter Roberson
on 12 Nov 2017

for k = 1:length(ar)

if ar(k)==243 % Using your example of the 243 element

posX=k;

break

else

continue

end

end

##### 0 Comments

### See Also

### Categories

### Community Treasure Hunt

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

Start Hunting!