| Contents [0/7] |
| Linear versus Constant Time [1/7] |
| PlaygroundSearch [2/7] |
| Linear search [3/7] |
| Demo from the textbook [4/7] |
| Binary search [5/7] |
| Printing lo and hi [6/7] |
| Printing lo and hi [7/7] |
(Click here for one slide per page)
| Linear versus Constant Time [1/7] |
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/7] |
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/7] |
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/7] |
| Binary search [5/7] |
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/7] |
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/7] |
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