Problem 5.2

Searching an unsorted array

The problem examines three algorithms for searching for a value $x$ in an unsorted array $A$ consisting for $n$ elements.

Consider the following randomized strategy: pick a random index $i$ into $A$. If $A[i] = x$, then we terminate; otherwise, we continue the search by picking a new random index into $A$. We continue picking random indices into $A$ until we find an index $j$ such that $A[j] = x$ or until we have checked every element of $A$. Note that we pick from the whole set of indices each time, so that we may examine a given element more than once.

  1. Write pseudocode for a procedure RANDOM-SEARCH to implement the strategy above. Be sure that your algorithm terminates when all indices into $A$ have been picked.
  2. Suppose that there is exactly one index $i$ such that $A[i] = x$. What is the expected number of indices into $A$ that we must pick before we find $x$ and RANDOM-SEARCH terminates?
  3. Generalizing your solution to part (b), suppose that there are $k \ge 1$ indices $i$ such that $A[i] = x$. What is the expected number of indices into $A$ that we must pick before we find $x$ and RANDOM-SEARCH terminates? Your answer should be a function of $n$ and $k$.
  4. Suppose that there are no indices $i$ such that $A[i] = x$. What is the expected number of indices into $A$ that we must pick before we have checked all elements of $A$ and RANDOM-SEARCH terminates?

Now consider a deterministic linear search algorithm, which we refer to as DETERMINISTIC-SEARCH. Specifically, the algorithm searches $A$ for $x$ in order, considering $A[1], A[2], A[3], \ldots, A[n]$ until either it finds $A[i] = x$ or it reaches the end of the array. Assume that possible permutations of the input array are equally likely.

  1. Suppose that there is exactly one index $i$ such that $A[i] = x$. What is the average-case running time of DETERMINISTIC-SEARCH? What is the worst-case running time of DETERMINISTIC-SEARCH?
  2. Generalizing your solution to part (e), suppose that there are $k \ge 1$ indices $i$ such that $A[i] = x$. What is the average-case running time of DETERMINISTIC-SEARCH? What is the worst-case running time of DETERMINISTIC-SEARCH? Your answer should be a function of $n$ and $k$.
  3. Suppose that there are no indices $i$ such that $A[i] = x$. What is the average-case running time of DETERMINISTIC-SEARCH? What is the worst-case running time of DETERMINISTIC-SEARCH?

Finally, consider a randomized algorithm SCRAMBLE-SEARCH that works by first randomly permuting the input array and then running the deterministic linear search given above on the resulting permuting array.

  1. Letting $k$ be the number of indices $i$ such that $A[i] = x$, give the worst-case and expected running time of SCRAMBLE-SEARCH for the cases in which $k = 0$ and $k = 1$. Generalizing your solution to handle the case in which $k \ge 1$.
  2. Which of the three searching algorithms would you use? Explain your answer.

RANDOM-SEARCH pseudocode

RANDOM-SEARCH(x, A, n):
  v = ∅
  while |∅| ≠ n
      i = RANDOM(1, n)
      if A[i] = x
          return i
      else:
          v = v ∩ i
  return ␀

v can be implemented in multiple ways - a hash table, a tree or a bitmap. The last one would probabily perform best and consume the least space.

RANDOM-SEARCH with one match

RANDOM-SEARCH is well-modelled by Bernoulli trials. The expected number of picks is $n$.

RANDOM-SEARCH with multiple matches

In similar fashion, the expected number of picks is $n/k$.

RANDOM-SEARCH with no matches

This is modelled by the balls and bins problem, explored in section 5.4.2. The answer is $n(\ln{n} + \O(1))$.

DETERMINISTIC-SEARCH with one match

The worst-case running time is $n$. The average-case is $(n+1)/2$ (obviously).

DETERMINISTIC-SEARCH with multiple matches

The worst-case running time is $n-k+1$. The average-case running time is $(n+1)/(k+1)$. Let $X_i$ be an indicator random variable that the $i$th element is a match. $\Pr\{X_i\} = 1/(k+1)$. Let $Y$ be an indicator random variable that we have found a match after the first $n-k+1$ elements ($\Pr\{Y\} = 1$). Thus:

$$ \E[X] = \E[X_1 + X_2 + \ldots + X_{n-k} + Y] = 1 + \sum_{i=1}^{n-k}\E[X_i] = 1 + \frac{n-k}{k+1} = \frac{n+1}{k+1} $$

DETERMINISTIC-SEARCH with no matches

Both the worst-case and average case is $n$.

SCRAMBLE-SEARCH matches

It's the same as DETERMINISTIC-SEARCH, only we replace "average-case" with "expected".

Best algorithm

Definitelly DETERMINISTIC-SEARCH. SCRAMBLE-SEARCH gives better expected results, but for the cost of randomly permuting the array, which is a linear operation. In the same time we could have scanned the full array and reported a result.