Archived

This topic is now archived and is closed to further replies.

malpass

Detecting number patterns in an array

Recommended Posts

I have a function that loops, adding a number to an array over and over (different number each time, say primes) and I want to detect fast on each phase of the loop if any number appears twice. How can I do this fast? For example int i=0; bool n = true; while(n) { i++; // Add i to array if () // if i appeared in array before {n=false;} } very rough but you get the idea. In that case it would be infinite because an incrementing i will never repeat a number twice.

Share this post


Link to post
Share on other sites
Keep the array sorted, do a binary search.

edit:
That is, I assume you want to make sure you don't push two identical values into the list.
If not, you can just keep it sorted anyway because that would make scanning for doubles quite easy(just look at the next number, if they are identical - remove one).

[edited by - Tjoppen on April 5, 2004 10:46:35 AM]

Share this post


Link to post
Share on other sites
A binary search will find the number 7 as being in the following array:

4, 6, 9, 14, 15, 17

returning the index 9. It searches single letters. So it isnt correct

Share this post


Link to post
Share on other sites
quote:
Original post by malpass
A binary search will find the number 7 as being in the following array:

4, 6, 9, 14, 15, 17

returning the index 9. It searches single letters. So it isnt correct


I don''t believe you fully understand what Tjoppen meant when he suggested using a binary search on an array of values. The search will not parse the int values into single digits.

Share this post


Link to post
Share on other sites

static ArrayList T(int x)
{
ArrayList A=new ArrayList();
int a=S(x);
A.Add(a);
while(A.BinarySearch(x)<0){a=S(a);if(A.BinarySearch(a)<0){A.Add(a);}else{break;}}
A.RemoveAt(A.Count-1);
return A;
}


A.BinarySearch(x)<0 will detect the initial value that isnt added to the Array, for duplicates, and A.BinarySearch(a)<0 will detect is the number about to be added is already in.

Yet A.BinarySearch(a)<0 returns 4 after a few loops of 49 97 130 10 1 1 1 1 1. And 4 is obviously the 7 in 97, so it _does_ search single digits, and I dont want it to do that

Edit: Another point being it doesnt even work because 1 is repeated several times, and it is never detected by A.BinarySearch(a)<0 it is only because A.BinarySearch(x)<0 returns 4, so somethings wrong here

[edited by - malpass on April 5, 2004 11:08:11 AM]

Share this post


Link to post
Share on other sites
Ahh, it seems that you are using ArrayList from Java or possible C#. I haven't looked into the implementation of BinarySearch for either of them, I was under the assumption from your psuedo-code that this was strictly a C/C++ array and you would be writing the binary search yourself. I really can't speak of the results of the BinarySearch function that I haven't seen.

Edit: I'd suggest looking closely at the documentation for the ArrayList BinarySearch function to see it is really the function you want to use. I'm sure both the Java and C# docs can be found online.

[edited by - MikeDulany on April 5, 2004 11:33:26 AM]

Share this post


Link to post
Share on other sites
well according to MSDN the Array.BinarySearch of C++ is identicle to C#''s. Do you know the structure of the BinarySearch then? so I can just make my own

Share this post


Link to post
Share on other sites
Google "C++ binary search" results

These pages should have some good examples of how a binary search should be implemented. Good luck!

[edited by - MikeDulany on April 5, 2004 11:49:09 AM]

Share this post


Link to post
Share on other sites