Contiguous sector (sub array)

Recommended Posts

VprMatrix89    100
I have a function that searches for a value in the array, and so far the only method I have is a long loop that searches the array top to bottom, there is a bit of optimization left by using a stride, but it still leaves much to be desired. Is there any other way to find a value in the array? Also, I should note that the value is completely random, so theres no way to tell the program where to look in the array. (i think)

Share this post

Share on other sites
Evil Steve    2017
Quote:
 Original post by VprMatrix89Is there any other way to find a value in the array?
Nope. If you're looking for a value in an un-sorted array, then the only way to do that is to do a linear search.

In what way would a stride help?

Share this post

Share on other sites
rip-off    10976
To search a non-sorted array, you are looking at an O(n) operation. That is, the top to bottom search is algorithmically optimal. If you are doing lots of search and relatively few insertions and updates, you could pre-sort the array, which is typically O(n log n) and then use a binary search O(log n) from then on.

Most languages have these kind of operations in their standard libraries.

If you aren't familiar with the notation above, read more here.

Share this post

Share on other sites
fpsgamer    856
If you have no knowledge of the ordering of elements in the array, the best you can possibly do is to search through all elements one by one. In the worst case this requires you to perform n comparisons, which is referred to as linear time.

The best you can do period is logarithmic time. It is known by a theorem that the lower bound running time of any comparison based search algorithm is O(log n).

So you can improve the speed of your search by storing your elements in a balanced binary tree structure which will ensure your elements are ordered. Now in the worst case you will perform log n comparisons in the worst case.

If you're using C++, std::map<> implements a balanced binary tree.

God damnit, I got ninja'ed.

Share this post

Share on other sites
VprMatrix89    100
Well I wanted to make a search algorithm but the problem is the size of the sector that contains contiguous information varies in size. Its basically storing a parent, atleast one pointer to a split, and a terminal, that can later be used to be a pointer to another fragment of the listed splits. The terminal also tells thats where the end of the list of the parent is.

The terminal is the last value that will not be used, and the pointer is added to this constant value.

The whole idea is to to not use a sector of 10 elements every single time when I can get by with 3 when needed. I can have another array that stores the tree, but I'm thinking right now there is an extremely complicated answer to this that im not yet understanding, by using the pointer to the last unused space in the array, I can reverse engineer the steps it took. Perhaps I must do this unless I want to use a top bottom search pattern.

Share this post

Share on other sites
Antheus    2409
Quote:
 Original post by rip-offTo search a non-sorted array, you are looking at an O(n) operation. That is, the top to bottom search is algorithmically optimal.

Well, there's always superlinear approach.

Quote:
 Well I wanted to make a search algorithm but the problem is the size of the sector that contains contiguous information varies in size. Its basically storing a parent, atleast one pointer to a split, and a terminal, that can later be used to be a pointer to another fragment of the listed splits. The terminal also tells thats where the end of the list of the parent is.

Somewhat complex...

Perhaps a B tree would do, or its variation applied to file systems.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now