# 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]

• Read Algorithms 1.4 again. Also read 2.1. Also read the discussion of stability in section 2.5 (page 341 in the third printing of the text).

• Do these problems on paper, but don't hand them in.
• 1.5.1
• 1.5.2
• 1.5.3
• Complete Percolation.java

 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)?

• Constant amount of time (1)
• Time proportional to the logorithm of the length of the list (log2 N)
• Time proportional to the length of the list (N)
• Time proportional to the length of the list squared (N2)
• Time proportional to the exponential of the length of the list squared (2N)

 ``` 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