CSC403: Binary Search (Review from DS1)

Contents [0/9]

Linear versus Constant Time [1/9]

PlaygroundSearch [2/9]

Linear search [3/9]

Slides from the textbook [4/9]

Binary search [5/9]

Printing lo and hi [6/9]

Printing lo and hi [7/9]

Linear search [8/9]

Binary search [9/9]

(Click here for one slide per page)

Linear versus Constant Time [1/9]

Accessing a linked list element is linear time

Accessing an array list element is constant time

See algs14.PlaygroundIndexing

Output

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/9]

See algs14.PlaygroundSearch

Note: doubleSortedUnique implementation for reference...

  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/9]

  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

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]

Slides from the textbook [4/9]

Demo: Binary Search

Here is an interesting video showing how to derive binary search in a fancy programming environment:

Binary search [5/9]

  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

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/9]

  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/9]

  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

Linear search [8/9]

  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

  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 (log₂ N)
Time proportional to the length of the list (N)
Time proportional to the length of the list squared (N²)
Time proportional to the exponential of the length of the list squared (2^N)

running-times

More graphs (also available here)

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 [9/9]

  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?

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