StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>If the buckets are contiguous and disjoint, as in your example, you need to store in a vector just the left bound of each bucket (i.e. 1, 5, 16, 22) plus, as the last element, the first number that doesn't fall in any bucket (35). (I assume, of course, that you are talking about <em>integer</em> numbers.)</p> <p>Keep the vector sorted. You can search the bucket in O(log n), with kind-of-binary search. To search which bucket does a number x belong to, just go for the only index i such that vector[i] <= x < vector[i+1]. If x is strictly less than vector[0], or if it is greater than or equal to the last element of vector, then no bucket contains it.</p> <p>EDIT. Here is what I mean:</p> <pre><code>#include <stdio.h> // ~ Binary search. Should be O(log n) int findBucket(int aNumber, int *leftBounds, int left, int right) { int middle; if(aNumber < leftBounds[left] || leftBounds[right] <= aNumber) // cannot find return -1; if(left + 1 == right) // found return left; middle = left + (right - left)/2; if( leftBounds[left] <= aNumber && aNumber < leftBounds[middle] ) return findBucket(aNumber, leftBounds, left, middle); else return findBucket(aNumber, leftBounds, middle, right); } #define NBUCKETS 12 int main(void) { int leftBounds[NBUCKETS+1] = {1, 4, 7, 15, 32, 36, 44, 55, 67, 68, 79, 99, 101}; // The buckets are 1-3, 4-6, 7-14, 15-31, ... int aNumber; for(aNumber = -3; aNumber < 103; aNumber++) { int index = findBucket(aNumber, leftBounds, 0, NBUCKETS); if(index < 0) printf("%d: Bucket not found\n", aNumber); else printf("%d belongs to the bucket %d-%d\n", aNumber, leftBounds[index], leftBounds[index+1]-1); } return 0; } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload