$ $

Example: Binary Search

• Here is a useful example of recursion:

  public static int binarySearch(int[] values, int target, 
                                 int start, int end) {
  
      if (start > end) {
          return -1;
      }
  
      int mid = (start + end) / 2;
  
      if (target == values[mid]) {
          return mid;
      } else if (target < values[mid]) {
          return binarySearch(values, target, start, mid - 1);
      } else {
          return binarySearch(values, target, mid + 1, end);
      }
  
  }

Informal Analysis of Binary Search

• Informally, we could just try some searches and see show long they take:

• Result:

  $n$	total equality checks
  1	1
  2	2
  4	3
  8	4

• Looks like ${\log }_{2}n+1$

• (For non-powers-of-two $\lfloor {\log }_{2}n\rfloor +1$)

Binary Search Recurrence

• Initial conditions:

  $W(1)=$ ??

• $W(1)=1$

• Recurrence:

  $W(n)=??$

• $W(n)=1+W(n/2)$

Example: Recursive Binary Search

• Worst-case recurrence:

  $W(1)=1$

  $W(n)=1+W(n/2)$

Example: Recursive Binary Search

• Worst-case recurrence:

  $W(1)=1$

  $W(n)=1+W(n/2)$

• We can use backward substitution to calcuate the value of the recurrence at particular values of $n$:
  • $W(8)=?$
  • $W(8)=1+W(4)$
  • $W(8)=1+(1+W(2))$
  • $W(8)=1+(1+(1+W(1)))$
  • $W(8)=4$

Example: Recursive Binary Search

Step 2: Backward Substitution

$W(1)=1$

$W(x)=1+W(x/2)$

Solve for $i$ that results in initial condition:

$\frac{n}{2^i}=1$

$n=2^i$

$i={\log }_{2}n$

Substitute ${\log }_{2}n$ for $i$:

$W(n)={\log }_{2}n+1$

Step 3: Check the Answer

Applying recurrence:

$W(1)=1$

$W(2)=1+W(1)=1+1=2$

$W(4)=1+W(2)=1+2=3$

Applying solution:

$W(1)={\log }_{2}1+1=0+1=1$

$W(2)={\log }_{2}2+1=1+1=2$

$W(4)={\log }_{4}4+1=2+1=3$

Steps to Analyzing a Recursive Algorithm

• Step 1: Develop a Recurrence (Last time)
• Step 2: Solving the Recurrence
  • One approach is the method of backward substitution:
    1. Expand the recurrence by repeated substitution until a pattern emerges.
    2. Characterize the pattern by expressing the recurrence in terms of $n$ and $i$, (where $i$ is the number of substitutions).
    3. Substitute for $i$ an expression that will remove the recursive term.
    4. Manipulate the result to achieve a closed-form solution.
• Step 3: Check Your Answer
  • Make sure that the recurrence and the closed form solution agree for several values of $n$.

Another Example:

count the comparison values[start] == values[end]

    public static boolean unique(int[] values, int start, int end) {
        if (start >= end) {
            return true;
        } else if (values[start] == values[end]) {
            return false;
        } else {
            return unique(values, start, end - 1) 
                    && unique(values, start + 1, end);
        }

    }

Part 1:

    public static boolean unique(int[] values, int start, int end) {
        if (start >= end) {
            return true;
        } else if (values[start] == values[end]) {
            return false;
        } else {
            return unique(values, start, end - 1) 
                    && unique(values, start + 1, end);
        }

    }

$W(1)=0$

$W(n)=1+2W(n-1)$

Part 2:

$W(1)=0$

$W(x)=1+2W(x-1)$

Solve for $i$ that results in initial condition:

$n-i=1$

$i=n-1$

Substitute $n-1$ for $i$:

$W(n)=2^{n-1}-1+2^{n-1}\times 0=2^{n-1}-1$

Part 3

Applying recurrence:

$W(1)=0$

$W(2)=1+2W(0)=1+0=1$

$W(3)=1+2W(1)=1+1=2$

$W(4)=1+2W(2)=1+2=3$

Applying solution:

$W(1)=2^{1-1}-1=0$

$W(2)=2^{2-1}-1=1$

$W(3)=2^{3-1}-1=3$