| Contents [0/8] |
| Linear versus Constant Time [1/8] |
| PlaygroundSearch [2/8] |
| Linear search [3/8] |
| Demo from the textbook [4/8] |
| Binary search [5/8] |
| Printing lo and hi [6/8] |
| Printing lo and hi [7/8] |
| Binary search [8/8] |
(Click here for one slide per page)
| Linear versus Constant Time [1/8] |
Accessing a linked list element is linear time
Accessing an array list element is constant time
See algs14.PlaygroundIndexing
Output searching for N (will be worst case, since N is at the end of the array or linked list!):
Linked elapsed count N= 512 [ 0.000 : NaN] Linked elapsed count N= 1,024 [ 0.000 : NaN] Linked elapsed count N= 2,048 [ 0.000 : NaN] Linked elapsed count N= 4,096 [ 0.000 : NaN] Linked elapsed count N= 8,192 [ 0.000 : NaN] Linked elapsed count N= 16,384 [ 0.000 : NaN] Linked elapsed count N= 32,768 [ 0.000 : NaN] Linked elapsed count N= 65,536 [ 0.001 : Infinity] Linked elapsed count N= 131,072 [ 0.001 : 1.000] Linked elapsed count N= 262,144 [ 0.002 : 2.000] Linked elapsed count N= 524,288 [ 0.003 : 1.500] Linked elapsed count N= 1,048,576 [ 0.005 : 1.667] Linked elapsed count N= 2,097,152 [ 0.010 : 2.000] Linked elapsed count N= 4,194,304 [ 0.024 : 2.400] Linked elapsed count N= 8,388,608 [ 0.075 : 3.125] Linked elapsed count N= 16,777,216 [ 0.151 : 2.013] Linked elapsed count N= 33,554,432 [ 0.211 : 1.397] Array elapsed count N= 512 [ 0.000 : NaN] Array elapsed count N= 1,024 [ 0.000 : NaN] Array elapsed count N= 2,048 [ 0.000 : NaN] Array elapsed count N= 4,096 [ 0.000 : NaN] Array elapsed count N= 8,192 [ 0.000 : NaN] Array elapsed count N= 16,384 [ 0.000 : NaN] Array elapsed count N= 32,768 [ 0.000 : NaN] Array elapsed count N= 65,536 [ 0.000 : NaN] Array elapsed count N= 131,072 [ 0.000 : NaN] Array elapsed count N= 262,144 [ 0.000 : NaN] Array elapsed count N= 524,288 [ 0.000 : NaN] Array elapsed count N= 1,048,576 [ 0.000 : NaN] Array elapsed count N= 2,097,152 [ 0.000 : NaN] Array elapsed count N= 4,194,304 [ 0.000 : NaN] Array elapsed count N= 8,388,608 [ 0.000 : NaN] Array elapsed count N= 16,777,216 [ 0.000 : NaN] Array elapsed count N= 33,554,432 [ 0.000 : NaN]
| PlaygroundSearch [2/8] |
See algs14.PlaygroundSearch
Note: doubleSortedUnique implementation for reference...
01 |
public static double[] doubleSortedUnique (int N) { if (N < 0) throw new IllegalArgumentException (); double[] a = new double[N]; for (int i = 0; i < N; i++) { a[i] = i; } return a; } |
| Linear search [3/8] |
01 |
public static boolean contains (double val, double[] list) { int lo = 0; int hi = list.length - 1; while (lo <= hi) { if (val != list[lo]) lo = lo + 1; else return true; } return false; } |
Output searching for N (will fail, N is not in the array!):
Finished tests Elapsed count N= 512 [ 0.000 : NaN] Elapsed count N= 1,024 [ 0.000 : NaN] Elapsed count N= 2,048 [ 0.000 : NaN] Elapsed count N= 4,096 [ 0.000 : NaN] Elapsed count N= 8,192 [ 0.000 : NaN] Elapsed count N= 16,384 [ 0.001 : Infinity] Elapsed count N= 32,768 [ 0.000 : 0.000] Elapsed count N= 65,536 [ 0.001 : Infinity] Elapsed count N= 131,072 [ 0.001 : 1.000] Elapsed count N= 262,144 [ 0.000 : 0.000] Elapsed count N= 524,288 [ 0.001 : Infinity] Elapsed count N= 1,048,576 [ 0.001 : 1.000] Elapsed count N= 2,097,152 [ 0.002 : 2.000] Elapsed count N= 4,194,304 [ 0.004 : 2.000] Elapsed count N= 8,388,608 [ 0.008 : 2.000] Elapsed count N= 16,777,216 [ 0.015 : 1.875] Elapsed count N= 33,554,432 [ 0.031 : 2.067] Elapsed count N= 67,108,864 [ 0.067 : 2.161] Elapsed count N= 134,217,728 [ 0.127 : 1.896] Elapsed count N= 268,435,456 [ 0.230 : 1.811]
| Demo from the textbook [4/8] |
| Binary search [5/8] |
01 |
public static boolean contains (double val, double[] list) { int lo = 0; int hi = list.length - 1; while (lo <= hi) { int mid = lo + (hi-lo)/2; if (val > list[mid]) lo = mid + 1; else if (val < list[mid]) hi = mid - 1; else return true; } return false; } |
Output searching for N (will fail, N is not in the array!):
Finished tests Elapsed count N= 512 [ 0.000 : NaN] Elapsed count N= 1,024 [ 0.000 : NaN] Elapsed count N= 2,048 [ 0.000 : NaN] Elapsed count N= 4,096 [ 0.000 : NaN] Elapsed count N= 8,192 [ 0.000 : NaN] Elapsed count N= 16,384 [ 0.000 : NaN] Elapsed count N= 32,768 [ 0.000 : NaN] Elapsed count N= 65,536 [ 0.000 : NaN] Elapsed count N= 131,072 [ 0.000 : NaN] Elapsed count N= 262,144 [ 0.000 : NaN] Elapsed count N= 524,288 [ 0.000 : NaN] Elapsed count N= 1,048,576 [ 0.000 : NaN] Elapsed count N= 2,097,152 [ 0.000 : NaN] Elapsed count N= 4,194,304 [ 0.000 : NaN] Elapsed count N= 8,388,608 [ 0.000 : NaN] Elapsed count N= 16,777,216 [ 0.000 : NaN] Elapsed count N= 33,554,432 [ 0.000 : NaN] Elapsed count N= 67,108,864 [ 0.000 : NaN] Elapsed count N= 134,217,728 [ 0.000 : NaN] Elapsed count N= 268,435,456 [ 0.000 : NaN]
| Printing lo and hi [6/8] |
01 |
public static boolean contains (double val, double[] list) { int lo = 0; int hi = list.length - 1; while (lo <= hi) { StdOut.format("%4d/%4d \n", lo, hi); int mid = lo + (hi-lo)/2; if (val > list[mid]) lo = mid + 1; else if (val < list[mid]) hi = mid - 1; else return true; } StdOut.format("%4d/%4d \n", lo, hi); return false; } |
Output
[0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0,... 0/1022 512/1022 768/1022 896/1022 960/1022 992/1022 1008/1022 1016/1022 1020/1022 // yes 0/1022 0/ 510 0/ 254 128/ 254 128/ 190 160/ 190 176/ 190 184/ 190 // yes 0/1022 0/ 510 0/ 254 0/ 126 0/ 62 32/ 62 32/ 46 32/ 38 36/ 38 38/ 38 39/ 38 // NO 0/1022 0/ 510 256/ 510 256/ 382 320/ 382 320/ 350 336/ 350 336/ 342 340/ 342 342/ 342 343/ 342 // NO 0/1022 0/ 510 256/ 510 256/ 382 320/ 382 320/ 350 336/ 350 336/ 342 336/ 338 338/ 338 339/ 338 // NO 0/1022 512/1022 768/1022 896/1022 896/ 958 896/ 926 896/ 910 904/ 910 904/ 906 904/ 904 904/ 903 // NO 0/1022 0/ 510 0/ 254 128/ 254 128/ 190 160/ 190 160/ 174 168/ 174 168/ 170 // yes 0/1022 0/ 510 0/ 254 0/ 126 0/ 62 32/ 62 32/ 46 40/ 46 44/ 46 46/ 46 // yes 0/1022 512/1022 768/1022 896/1022 896/ 958 896/ 926 912/ 926 912/ 918 916/ 918 918/ 918 919/ 918 // NO 0/1022 512/1022 512/ 766 512/ 638 512/ 574 512/ 542 528/ 542 528/ 534 532/ 534 532/ 532 // yes found 5/ 10
| Printing lo and hi [7/8] |
01 |
public static boolean contains (double val, double[] list) { int lo = 0; int hi = list.length - 1; while (lo <= hi) { StdOut.format("%4d ", hi-lo+1); int mid = lo + (hi-lo)/2; if (val > list[mid]) lo = mid + 1; else if (val < list[mid]) hi = mid - 1; else return true; } StdOut.format("%4d ", hi-lo+1); return false; } |
Output
[0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0,... 1023 511 255 127 63 31 15 7 // yes 1023 511 255 127 63 31 15 7 3 1 // yes 1023 511 255 127 63 31 15 7 3 1 0 // NO 1023 511 255 127 63 31 15 7 3 1 0 // NO 1023 511 255 127 63 31 15 7 // yes 1023 511 255 127 63 31 15 7 3 1 // yes 1023 511 255 127 63 31 15 7 3 1 0 // NO 1023 511 255 127 63 31 15 7 3 1 0 // NO 1023 511 255 127 63 31 15 7 3 1 0 // NO 1023 511 255 127 63 31 15 7 3 1 // yes found 5/ 10
| Binary search [8/8] |
01 |
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 |
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"); } } |