Searching a value in an array of ranges.

I don't need split - this is array of structures (or 2D array or classes or whatever)
According NTFS docs, a volume can contain up to 2^64 files. Usually there are some hundreds K records (up to 1M records) in MFT. Each record contains attributes. Each non-resident attribute contains 1 or more data runs (sometimes more then 10). So array can contains up to 10M elements (or even more). I need to get MFT record Info (all MFT records already stored in array) pointing on logical cluster by mouse pointer, so time limit is about 0.5 sec

ozo, thanks for suggestion
I've implemented your idea, but it's toooo slow for huge arrays.
Currently I stops with 'self-linked' structures:

Private Type CLUSTERS_BLOCK
   blockIndex As Long 'self array index
   startLCN As Long    'range start
   endLCN As Long     'range end
   attrType As Byte  'inner data
   mftRecordNum As Long 'inner data
   crossLinksCount As Long 'number of relative ranges
   crossLinkIndex() As Long 'relative ranges indexes
End Type

When adding elements to array (unsorted), I set startLCN, endLCN and inner data. Then sort array by startLCN (QuickSort is really fast!). Then, looping trough sorted array (For...Next) starting from first record:
1. Set blockIndex = i
2. Check if next record (i + 1) intersect with current (next startLCN between start and end for current). If so
   2.1. increase crossLinksCount for current, add next index  (i + 1) crossLinkIndex to index array
   2.2. increase crossLinksCount for next, add current  index (i) crossLinkIndex to index array
3. If current record already have crossLinks (added during previous step when it was 'next' - check all crossLinks against 'next' and, if they intersects, add to 'nex' crossLinkIndex array
Then I use Binary Search to get exact or nearest smaller record. Searching all cross links indexes I get all ranges.
Timings are (300K records):
Sorting, parsing - each about 5 secs.
Searching - about 50-100 millisecond
Your approach:
Sorting - same
Then splitting into small  ranges - up to 2 mins due to huge memory moving when inserting new values into array
Splitting and sorting 'inline', when adding records - a bit faster, but anyway more then 1 min/
Both solutions (your and mine) are very memory hungry and eats some hundreds MB. Unfortunately, VB6 doesn't allow self-relative structures like .NET o C++ does
struct ClusterBlock {
  struct ClusterBlock *Next
  struct ClusterBlock *Prev
}
which can save some memory.
I hope there is some math algorithm which allow to search those range array (smth like nearest neighbor or similar) without adding extra indexes array into structure.

Regards
Ark  

slow to build or slow to search?
binary search should be fast, and I got the impression that search time was more important than build time.
There should be no more than twice as many entries in the nonintersecting ranges than the original list of intersecting ranges, (especially if you only need 2 ranges the value belongs to)
so building should be linear in the size of the original. list, or  n log n if you need to sort

Hi, ozo
You're right, searching is the key, but building also shouldn't be toooo slow!
Imagine ranges
1-100,000
5-5
15-15
20-20
25-25
etc 10,000 times
BTW, this is 'normal ' drive map when one huge file overwrites small deleted records (temp IE files, for example)
so, after sorting, I loop through ranges array and found 5-5 range. What should I do?
1. Redim Preserve MyArray (Ubound(MyArray)+2) 'this is not a problem, I can redim by chinks:
If Ubound()> someValue then RedimPreserve MyArra(ubound+1000) somevalue=somevalue+1000
2. Truncate lefValue: .EndPos=5 (instead of 100,000 previous)
3. Move all other elements to the right
   copyMemory MyArray(foundpos+1),myArray(foundPos),nElement * 4
4. Set inserted element (5-5)
5. set right element (5-100,000)

As for my code  -I don't need move/truncate/rearrange array elements. - first element will contain 10,000 indexes for each small range, and all smal will contain 1 index to large.

Now I'm nearly satisfy with my code unless smbd offer smth better. If no, you'll get your points :)

> Move all other elements to the right
I expect that this is what's making it slow

You're right. I also tried adding new elements to the end and then sorting again - it's a bit faster.