CSC300: Induction: Linear search [6/15] Previous pageContentsNext page

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");
  }
}

Previous pageContentsNext page