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