Find the bucket | Yaozong's Blog
Given an array of numbers, they are arranged so that the a[0] is in the 1st bucket, a[1]a[2] are in the 2nd bucket, a[3]a[4]a[5] is in the 3rd bucket and so on.
All the numbers in one bucket are larger than that of the previous bucket. So ALL numbers of bucket 3 will be bigger than ANY number of the bucket 2 and so on.
The number given to the function may or may not be in the array. The question is then: given a number, you need to return the bucket index if it is in any bucket. Otherwise, return -1 if this number is not in any of bucket.
Given an array of numbers, they are arranged so that the a[0] is in the 1st bucket, a[1]a[2] are in the 2nd bucket, a[3]a[4]a[5] is in the 3rd bucket and so on.
All the numbers in one bucket are larger than that of the previous bucket. So ALL numbers of bucket 3 will be bigger than ANY number of the bucket 2 and so on.
The number given to the function may or may not be in the array. The question is then: given a number, you need to return the bucket index if it is in any bucket. Otherwise, return -1 if this number is not in any of bucket.
bucket 0: [1]
bucket 1: [3, 4]
bucket 2: [7, 5, 6]
bucket 3: [20, 9, 8, 15]
bucket 4: [100, 85, 50, 22]
Input: [1, 3, 4, 7, 5, 6, 20, 9, 8, 15, 100, 85, 50, 22], 8
Output: 3
Input: [1, 3, 4, 7, 5, 6, 20, 9, 8, 15, 100, 85, 50, 22], 10
Output: -1
Input: [1, 3, 4, 7, 5, 6, 20, 9, 8, 15, 100, 85, 50, 22], 101
Output: -1
Solution: Binary Search
int find_bucket(vector<int>& arr, int target)
{
vector<int> buckets;
int i = 0, start = 0;
while(start < arr.size()) {
buckets.push_back(arr[start]);
++ i;
start = (i + 1) * i / 2;
}
// potential buckets
int lower = -1, upper = -1;
// binary search to find the upper-bound buckets
int left = 0, right = buckets.size() - 1;
while(left < right) {
int mid = (left + right) / 2;
if(buckets[mid] < target)
left = mid + 1;
else if(buckets[mid] == target)
return mid;
else
right = mid;
}
lower = left - 1; upper = left;
// linear search lower bucket
if(lower >= 0 && lower < buckets.size()) {
int start = (lower + 1) * lower / 2;
int end = min<int>(start + lower, arr.size()-1);
for(int i = start; i <= end; ++i) {
if(arr[i] == target)
return lower;
}
}
// linear search upper bucket
if(upper >= 0 && upper < buckets.size()) {
int start = (upper + 1) * upper / 2;
int end = min<int>(start + upper, arr.size()-1);
for(int i = start; i <= end; ++i) {
if(arr[i] == target)
return upper;
}
}
return -1;
}
Read full article from Find the bucket | Yaozong's Blog