WT*

p-ary search

Given is a strictly increasing sequence of integers A, an integer y, and a parameter p. The task is to find the position of y in A (or -1 if it is not there) in time O(log n / log p) and work O(p log n/log p).

We use the idea of binary search generalized to p processors: to search for y in an interval l-r of the array, we divide the interval into p+1 buckets, and check in parallel which bucket could contain y. Since the sequence is strictly increasing, there is no conflict in writing the index of the bucket to a shared variable. Next, we recursively search within the selected bucket.

input int A[_], y, p;
output int result;
int n = A.size;
int B[n + 2];

int search(int l, int r) {
  int n = r - l + 1;
  int result = -1;

  if (p >= n) {
    pardo(i : n) if (B[l + i] == y) result = l + i;
    return result;
  }
  int q = n / (p + 1);
  int bucket = -1;
  pardo(i : p) {
    int mypos = l + (i + 1) * q - 1;
    if (B[mypos] == y)
      result = mypos;
    else if (B[mypos] > y && B[mypos - q] < y)
      bucket = mypos;
  }
  if (result != -1) return result;
  if (bucket == -1)
    return search(l + p * q, r);
  else
    return search(bucket - q + 1, bucket);
}

if (y > A[n - 1])
  result = -1;
else if (y == A[n - 1])
  result = n - 1;
else {
  B[0] = -99999;
  B[n + 1] = 99999;
  pardo(i : n) B[i + 1] = A[i];
  result = search(1, n);
  if (result > 0) result--;
}