Detecting number patterns in an array
Author
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.
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]
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]
Author
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
4, 6, 9, 14, 15, 17
returning the index 9. It searches single letters. So it isnt correct
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.
Author
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]
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]
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]
Author
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
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]
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]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
