CSC300: Binary Search

Contents [0/8]

Video [1/8]
Slides from the textbook [2/8]
Linear versus Constant Time [3/8]
PlaygroundSearch [4/8]
Linear search [5/8]
Binary search [6/8]
Printing lo and hi [7/8]
Printing lo and hi [8/8]

(Click here for one slide per page)


Video [1/8]

Open Playlist

00:00 Indexing an array is constant time
02:43 The search problem in a sorted array
03:35 The linear search algorithm
04:55 Thinking about a million filing cabinets
07:03 Watching the running time of binary search
08:18 Understanding binary search: success case
11:16 Understanding binary search: failure case
12:15 Coding binary search
13:01 Printing lo and hi on random inputs
14:56 Printing the number of elements left in consideration
16:33 Time complexity of linear and binary search

Slides from the textbook [2/8]

Demo: Binary Search

Here is an interesting video showing how to derive binary search in a fancy programming environment: Bret Victor - Inventing on Principle

Linear versus Constant Time [3/8]

Accessing a linked list element is linear time

Accessing an array list element is constant time

file:PlaygroundIndexing.java [source] [doc-public] [doc-private]
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
37
38
39
40
41
42
43
 
package algs14;
import java.util.*;
import stdlib.*;
public class PlaygroundIndexing { 
  public static void main (String[] args) {
    ArrayList<Integer> array =  new ArrayList<>();
    LinkedList<Integer> linked =  new LinkedList<>();
    int size = 60_000_000;
    for (int i=1; i<=size; i++) {
      array.add(i);
      linked.add(i);
    }
    
    int MIN = 256;
    int MAX = size;
    double prevTime = performanceLinked (linked, MIN);
    for (int N = MIN*2; N <= MAX; N=N*2) {
      double time = performanceLinked (linked, N);
      StdOut.format ("Linked elapsed count N=%,13d [%10.3f : %10.3f]\n", N, time, time/prevTime);
      prevTime = time;
    }

    MIN = 256;
    MAX = size;
    prevTime = performanceArray (array, MIN);
    for (int N = MIN*2; N <= MAX; N=N*2) {
      double time = performanceArray (array, N);
      StdOut.format ("Array  elapsed count N=%,13d [%10.3f : %10.3f]\n", N, time, time/prevTime);
      prevTime = time;
    }
  }
  private static double performanceLinked (LinkedList<Integer> linked, int N) {
    Stopwatch sw = new Stopwatch ();
    linked.get(N);
    return sw.elapsedTime ();
  }
  private static double performanceArray (ArrayList<Integer> linked, int N) {
    Stopwatch sw = new Stopwatch ();
    linked.get(N);
    return sw.elapsedTime ();
  }
  
}

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 [4/8]

file:PlaygroundSearch.java [source] [doc-public] [doc-private]
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
 
package algs14;
import java.util.Arrays;
import stdlib.*;

public class PlaygroundSearch {
  /* Return true if val is in the list */
  public static boolean contains (double val, double[] list) {
    return StdRandom.bernoulli(); // TODO
  }

  public static void main (String[] args) {
    //printTest(1023);
    correctnessTest();
    performanceTest();
  } 
  private static void correctnessTest () {    
    correctnessHelper (true,  11, new double[] { 11, 21, 31, 41, 51, 61, 71 });
    correctnessHelper (true,  21, new double[] { 11, 21, 31, 41, 51, 61, 71 });
    correctnessHelper (true,  31, new double[] { 11, 21, 31, 41, 51, 61, 71 });
    correctnessHelper (true,  41, new double[] { 11, 21, 31, 41, 51, 61, 71 });
    correctnessHelper (true,  51, new double[] { 11, 21, 31, 41, 51, 61, 71 });
    correctnessHelper (true,  61, new double[] { 11, 21, 31, 41, 51, 61, 71 });
    correctnessHelper (true,  71, new double[] { 11, 21, 31, 41, 51, 61, 71 });
    correctnessHelper (false, 10, new double[] { 11, 21, 31, 41, 51, 61, 71 });
    correctnessHelper (false, 20, new double[] { 11, 21, 31, 41, 51, 61, 71 });
    correctnessHelper (false, 30, new double[] { 11, 21, 31, 41, 51, 61, 71 });
    correctnessHelper (false, 40, new double[] { 11, 21, 31, 41, 51, 61, 71 });
    correctnessHelper (false, 50, new double[] { 11, 21, 31, 41, 51, 61, 71 });
    correctnessHelper (false, 60, new double[] { 11, 21, 31, 41, 51, 61, 71 });
    correctnessHelper (false, 70, new double[] { 11, 21, 31, 41, 51, 61, 71 });
    correctnessHelper (false, 80, new double[] { 11, 21, 31, 41, 51, 61, 71 });        
    correctnessHelper (true,  11, new double[] { 11, 21, 31, 41, 51, 61 });
    correctnessHelper (true,  21, new double[] { 11, 21, 31, 41, 51, 61 });
    correctnessHelper (true,  31, new double[] { 11, 21, 31, 41, 51, 61 });
    correctnessHelper (true,  41, new double[] { 11, 21, 31, 41, 51, 61 });
    correctnessHelper (true,  51, new double[] { 11, 21, 31, 41, 51, 61 });
    correctnessHelper (true,  61, new double[] { 11, 21, 31, 41, 51, 61 });
    correctnessHelper (false, 10, new double[] { 11, 21, 31, 41, 51, 61 });
    correctnessHelper (false, 20, new double[] { 11, 21, 31, 41, 51, 61 });
    correctnessHelper (false, 30, new double[] { 11, 21, 31, 41, 51, 61 });
    correctnessHelper (false, 40, new double[] { 11, 21, 31, 41, 51, 61 });
    correctnessHelper (false, 50, new double[] { 11, 21, 31, 41, 51, 61 });
    correctnessHelper (false, 60, new double[] { 11, 21, 31, 41, 51, 61 });
    correctnessHelper (false, 70, new double[] { 11, 21, 31, 41, 51, 61 });
    correctnessHelper (false,  0, new double[] { });        
    correctnessHelper (true,  11, new double[] { 11 });        
    correctnessHelper (false, 10, new double[] { 11 });        
    correctnessHelper (false, 20, new double[] { 11 }); 
    correctnessHelper (true,  11, new double[] { 11, 21 });        
    correctnessHelper (true,  21, new double[] { 11, 21 });        
    correctnessHelper (false, 10, new double[] { 11, 21 });        
    correctnessHelper (false, 20, new double[] { 11, 21 }); 
    correctnessHelper (false, 30, new double[] { 11, 21 }); 
    StdOut.println ("Finished tests");
  }
  private static void correctnessHelper (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));
    }
  }
  private static void performanceTest () {
    int MIN = 256; // for powers of ten, start with 500L
    int MAX = 320000000;
    double prevTime = performanceHelper(MIN);
    for (int N = MIN*2; N <= MAX; N=N*2) {
      double time = performanceHelper(N);
      StdOut.format ("Elapsed count N=%,13d [%10.3f : %10.3f]\n", N, time, time/prevTime);
      prevTime = time;
    }
  }
  private static double performanceHelper (int N) {
    double[] list = ArrayGenerator.doubleRandomUnique(N);
    //double val = StdRandom.uniform (N); // gauranteed to succeed
    double val = N; // gauranteed to fail
    Stopwatch sw = new Stopwatch ();
    contains (val, list);
    return sw.elapsedTime ();
  }
  
  // To print values, paste these in the code:
  // StdOut.format("%4d/%4d \n", lo, hi);
  // StdOut.format("%4d ", hi-lo+1);
  private static void printTest (int N) {
    double[] list = ArrayGenerator.doubleSortedUnique(N);
    StdOut.println (Arrays.toString(list).substring(0, 50) + "...");
    int found = 0;
    int count = 10;
    for (int i=1; i<=count; i++) {
      double val = StdRandom.uniform (N+1);
      if (StdRandom.bernoulli()) 
        val = val - 0.5;
      if (contains (val, list))
        found = found + 1;
      StdOut.println();
    }
    StdOut.format("found %4d/%4d", found, count);
  } 
}

Note: I recently fixed a bug in stdlib.ArrayGenerator:

01
02
03
04
05
06
07
08
 
  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 [5/8]

01
02
03
04
05
06
07
08
09
10
11
12
13
 
  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]

Binary search [6/8]

01
02
03
04
05
06
07
08
09
10
11
12
13
 
  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 [7/8]

01
02
03
04
05
06
07
08
09
10
11
12
13
 
  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 [8/8]

01
02
03
04
05
06
07
08
09
10
11
12
13
 
  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

Revised: 2008/03/17 13:01