CSC300: Lecture 7 (More Analysis, Unions Find (1.4, 1.5))

Contents [0/3]

Homework [1/3]
Linear search [2/3]
Binary search [3/3]

Homework [1/3]

Linear search [2/3]

01
02
03
04
05
06
07
08
  public static boolean contains (double val, double[] list) {
    int i = 0;
    while (i < list.length) {
      if (val == list[i]) { return true; }
      i++;
    }
    return false;
  }

Another version

01
02
03
04
05
06
07
08
09
  public static boolean contains (double val, double[] list) {
    int i = 0;
    boolean result = false;
    while (i < list.length) {
      if (val == list[i]) { result = false; break; }
      i++;
    }
    return result;
  }

How long does it take (in the worst case)?

running-times

More graphs (also available here)

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
package algs11;
import java.util.Arrays;
import stdlib.*;

public class Playground {
  /* Return true if val is in the list */
  public static boolean contains (double val, double[] list) {
    return StdRandom.bernoulli (); //TODO: fix this
  }
  /* This is a test function */
  public static void testContains (boolean expected, double val, double[] list) {
    boolean actual = contains (val, list);
    if (expected != actual) {
      StdOut.format ("Failed: Expecting [%b] Actual [%b] with argument (%f, %s)\n", expected, actual, val, Arrays.toString (list));
    }
  }
  /* A main function for testing */
  public static void main (String[] args) {        
    for (double v : new double[] { 5, 7 }) {
      testContains (true, v, new double[] { 11, 21, 31, v, 41 });
      testContains (true, v, new double[] { v, 11, 21, 31, 41 });
      testContains (true, v, new double[] { 11, 21, 31, 41, v });
      testContains (true, v, new double[] { 11, v, 21, v, 31, 41 });
      testContains (true, v, new double[] { v });
      testContains (true, v, new double[] { v, v });
      testContains (false, v, new double[] { 11, 21, 31, 41 });
      testContains (false, v, new double[] { 11 });
      testContains (false, v, new double[] {});
    }
    StdOut.println ("Finished tests");
  }
}

Binary search [3/3]

01
02
03
04
05
06
07
08
09
10
11
  public static boolean contains(double val, double[] list) {
    int lo = 0;
    int hi = list.length-1;
    while (hi >= lo) {
      int mid = lo + (hi-lo)/2;
      if (val > list[mid]) lo = mid + 1;
      if (val < list[mid]) hi = mid - 1;
      if (val == list[mid]) return true;
    }
    return false;
  }

A more complicated pattern. Does it terminate? Under what assumptions?

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
package algs11;
import java.util.Arrays;
import stdlib.*;

public class Playground {
  /* Return true if val is in the list */
  public static boolean contains (double val, double[] list) {
    return StdRandom.bernoulli (); //TODO: fix this
  }
  /* This is a test function */
  public static void testContains (boolean expected, double val, double[] list) {
    boolean actual = contains (val, list);
    if (expected != actual) {
      StdOut.format ("Failed: Expecting [%b] Actual [%b] with argument (%f, %s)\n", expected, actual, val, Arrays.toString (list));
    }
  }
  /* A main function for testing */
  public static void main (String[] args) {        
    testContains (true, 11, new double[] { 11, 21, 31, 41, 51, 61, 71 });
    testContains (true, 21, new double[] { 11, 21, 31, 41, 51, 61, 71 });
    testContains (true, 31, new double[] { 11, 21, 31, 41, 51, 61, 71 });
    testContains (true, 41, new double[] { 11, 21, 31, 41, 51, 61, 71 });
    testContains (true, 51, new double[] { 11, 21, 31, 41, 51, 61, 71 });
    testContains (true, 61, new double[] { 11, 21, 31, 41, 51, 61, 71 });
    testContains (true, 71, new double[] { 11, 21, 31, 41, 51, 61, 71 });
    testContains (false, 10, new double[] { 11, 21, 31, 41, 51, 61, 71 });
    testContains (false, 20, new double[] { 11, 21, 31, 41, 51, 61, 71 });
    testContains (false, 30, new double[] { 11, 21, 31, 41, 51, 61, 71 });
    testContains (false, 40, new double[] { 11, 21, 31, 41, 51, 61, 71 });
    testContains (false, 50, new double[] { 11, 21, 31, 41, 51, 61, 71 });
    testContains (false, 60, new double[] { 11, 21, 31, 41, 51, 61, 71 });
    testContains (false, 70, new double[] { 11, 21, 31, 41, 51, 61, 71 });
    testContains (false, 80, new double[] { 11, 21, 31, 41, 51, 61, 71 });        
    StdOut.println ("Finished tests");
  }
}

Revised: 2008/03/17 13:01