8.7. Search Algorithms

Search algorithms

---

A search algorithm searches through a sequence of values looking for a value that has a particular property. There are usually two possible outcomes.

1. A value with the desired property is found. In that case, there is no need to search further.

2. The entire sequence is searched without finding a suitable value.

Notice that in one case, where a sought value is found, the search algorithm can stop the search early, and does not need to look at the entire sequence. In the other case, the algorithm needs to look at the entire sequence.

Examples using loops

---

nextprime(n) returns the smallest prime number that is greater than n. Notice that there will always exist such a prime number (assuming no integer overflow) so, in this case, there is no need to worry about what to do if no sought for value is found.

  long nextprime(long n)
  {
    for(int i = n+1; !isPrime(i); i++) {}
    return i;
  }

Now let's try an algorithm that can fail to find what it is searching for. member(x,A,n) returns true if one of the values A[0], A[1], ... A[n−1] is equal to x.

  bool member(int x, int A[], int n)
  {
    for(int i = 0; i < n; i++)
    {
      if(A[i] == x)
      {
        return true;
      }
    }
    return false;
  }

Now let's look at a problem that, at first glance, might not look like a search problem at all. allPositive(A,n) returns true if every one of A[0], A[1], ..., A[n−1] is a positive number. This is a search problem because it is searching for a number that is not positive. If it finds one, then the answer is obviously false, and the algorithm can stop without looking at the entire array.

  bool allPositive(int A[], int n)
  {
    for(int i = 0; i < n; i++)
    {
      if(A[i] <= 0)
      {
        return false;
      }
    }
    return true;
  }

Examples using recursion

---

Here are implementations of the above functions that use recursion in place of loops. Notice that there are three cases in the definitions of member and allPositive. There is a case where the answer is immediately seen to be true, one where the answer is immediately seen to be false, and one where the answer relies on a recursive call.

  long nextprime(long n)
  {
    if(isPrime(n+1))
    {
      return n+1;
    }
    else
    {
      return nextprime(n+1);
    }
  }

  bool member(int x, int A[], int n)
  {
    if(n == 0)
    {
      return false;
    }
    else if(A[n-1] == x)
    {
      return true;
    }
    else
    {
      return member(x, A, n-1);
    }
  }

  bool allPositive(int A[], int n)
  {
    if(n == 0)
    {
      return true;
    }
    else if(A[n-1] <= 0)
    {
      return false;
    }
    else
    {
      return allPositive(A, n-1);
    }
  }

Exercises

---

1. Write a definition of function firstPositive(A,n), which returns the first positive number in list A[0], ..., A[n-1], or returns 0 if none of those numbers is positive. Use a loop.

   Assume that n has type int and that A is an array of ints. firstPositive(A,0) should return 0.

   Answer

2. Solve the previous question, but this time use recursion instead of a loop. Answer

3. Write a definition of function allPrime(A,n), which returns true if all of A[0], ..., A[n-1] are prime numbers, and returns false otherwise. Use a loop. Assume that A is an array of ints and use function isPrime(n) to tell if n is prime. Answer

4. Write a definition of allPrime(A,n) from the preceding question, but use recursion instead of a loop. Answer

Search algorithm requirement

---

In our programming assignment submissions, you are required to use a search algorithm to solve a problem that is a search problem. For example, the following solves a search problem by a scan algorithm, and will lose 1-3 points. It counts the number of positive values in an A[1,...,n-1] and says that they are all positive if the count is n.

  bool allPositive(int A[], int n)
  {
    count = 0;
    for(int i = 0; i < n; i++)
    {
      if(A[i] > 0)
      {
        count++;
      }
    }
    return (count == n);
  }