EECE 230 Lecture Slides Program Efficiency, Spring 2019

Introduction to Computation and Programming Program Efficiency, Binary Search, and Insertion Sort EECE 230 - Introduction to Computation and Programming Slides prepared for EECE 230C, Fall 2018-19, MSFEA, AUB Updated with minor edits during the offering of EECE 230, Spring 2018-19, MSFEA, AUB Material in these slides is based on [Guttag, Chapter 9], [CLRS, Chapters 1 and 2], and wiki.python.org Reading: [Guttag, Chapter 9], [CLRS, Chap 1, Sections 2.1, 3.1] [CLRS] (AUB E-book link) : “Introduction to Algorithms”, by T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, MIT press, third edition, 2009, MIT press. Outline • Program efficiency, algorithmic complexity • Asymptotic notations: Theta, Big O, little o • Time of analysis of: Linear search Element distinctness Programming Assignment 2 algorithms • Binary Search • Insertion Sort • Time analysis of some list operations and methods EECE 230 - Introduction to Computation and Programming I II III I.1 Getting started: linear search • Let 𝑇(𝑛) = worst case running time of linearSearch on a size- 𝑛 list • Worst case: Adversary chooses L and e • Why worst case? It gives a guarantee EECE 230 - Introduction to Computation and Programming • Consider the linear search function (from PSS 4, while loops version): • If e is in L, function returns index of first occurrence returned. Otherwise, it returns -1 Problem Solving Session I.1 Getting started: linear search (Continued) EECE 230 - Introduction to Computation and Programming c1 c2 c3 c4 c5 c6 c7 c8 • Denote the cost, i.e., time, of Line 𝑖 by c𝑖 • Worst case? if e not in L • Thus (worst case) time: I.1 Getting started: linear search (Continued) 𝑇 𝑛 = 𝑐1 + 𝑐2 +𝑐3 + 𝑐4 + 𝑐5 +𝑐7 × 𝑛 + 𝑐4 +𝑐8 = 𝑐4 + 𝑐5 +𝑐7 × 𝑛 + (𝑐1+𝑐2 +𝑐3 + 𝑐4 +𝑐8 ) = a constant × 𝑛 + (a negligable term comapred to 𝑛 ) EECE 230 - Introduction to Computation and Programming c1 c2 c3 c4 c5 c6 c7 c8 • Denote the cost, i.e., time, of Line 𝑖 by c𝑖 • Worst case if e not in L • Thus (worst case) time: I.1 Getting started: linear search (Continued) 𝑇 𝑛 = 𝑐1 + 𝑐2 +𝑐3 + 𝑐4 + 𝑐5 +𝑐7 × 𝑛 + 𝑐4 +𝑐8 = 𝑐4 + 𝑐5 +𝑐7 × 𝑛 + (𝑐1+𝑐2 +𝑐3 + 𝑐4 +𝑐8 ) = a constant × 𝑛 + (a negligable term comapred to 𝑛 ) EECE 230 - Introduction to Computation and Programming c1 c2 c3 c4 c5 c6 c7 c8 • Denote the cost, i.e., time, of Line 𝑖 by c𝑖 • Worst case if e not in L • Thus (worst case) time: When while breaks at i=n I.2 Asymptotic analysis • We can’t measure the running exactly as it depends on  Interpreter’s implementation  Computer speed • Solution: asymptotic analysis: look at growth of 𝑇(𝑛) as the input size 𝒏 → ∞ • How does 𝑇(𝑛) scale as input size 𝑛 doubles or gets multiplied by 10? • Interested in the complexity of the algorithm and not its implementation using a particular programming language or its speed on a specific machine • Key:  Ignore constants  Ignore low order terms EECE 230 - Introduction to Computation and Programming I.2 Asymptotic analysis (Continued) • Examples: 5 × 𝑛 + 17 6 × 𝑛2 +18 × 𝑛 + 5 • Theta notation: • 5 × 𝑛 + 17 • 6 × 𝑛2 +18 × 𝑛 + 5 • 3 × log 𝑛 + 7 • 10 EECE 230 - Introduction to Computation and Programming Low order terms Constant Constant 1.2 Asymptotic analysis (Continued) • Examples: 5 × 𝑛 + 17 6 × 𝑛2 +18 × 𝑛 + 5 • Theta notation: • 5 × 𝑛 + 17 = Θ 𝑛 • 6 × 𝑛2 +18 × 𝑛 + 5 = Θ 𝑛2 • 3 × log 𝑛 + 7 = Θ log 𝑛 • 10 = Θ 1 EECE 230 - Introduction to Computation and Programming Low order terms Constant Constant 1.3 Theta notation: formal definition • Definition: Let f 𝑛 and g 𝑛 be functions defined on the nonnegative integers and taking real values. Assume that for 𝑛 large enough, f 𝑛 ≥ 0 and g 𝑛 ≥ 0. We say that f 𝑛 = Θ 𝑔 𝑛 if lim 𝑛→∞ 𝑓 𝑛 𝑔 𝑛 = a positive constant assuming that the limit exists. • Check above examples: EECE 230 - Introduction to Computation and Programming 1.3 Theta notation: formal definition (Continued) EECE 230 - Introduction to Computation and Programming • Check above examples: lim 𝑛→∞ 5×𝑛+17 𝑛 = 5 > 0 => 5 × 𝑛 + 17 = Θ 𝑛 lim 𝑛→∞ 6× 𝑛2+18×𝑛+5 𝑛2 = 6 > 0 => 6 × 𝑛2 +18 × 𝑛 + 5 = Θ 𝑛2 lim 𝑛→∞ 3×log 𝑛+7 log 𝑛 = 3 > 0 => 3 × log 𝑛 + 7 = Θ log 𝑛 lim 𝑛→∞ 10 1 = 10 > 0 => 10 = Θ 1 I.4 Theta notation: more formal definition More generally (even if limit doesn’t exist), we say that f 𝑛 = Θ 𝑔 𝑛 if for large values of n, f 𝑛 can be sandwiched between two positive constant multiples of g(n), i.e., there exist 𝑛0 > 0 and constants c1, 𝑐2 > 0 such that for all 𝑛 > 𝑛0, 0 ≤ 𝑐1 × 𝑔 𝑛 ≤ f 𝑛 ≤ 𝑐2 × 𝑔 𝑛 EECE 230 - Introduction to Computation and Programming [Figure 3.1 in “Introduction to Algorithms”, Cormen, Leriseron, Rivest, and Stein, 2009] I.4 Theta notation: more formal definition More generally (even if limit doesn’t exist), we say that f 𝑛 = Θ 𝑔 𝑛 if for large values of n, f 𝑛 can be sandwiched between two positive constant multiples of g(n), i.e., there exist 𝑛0 > 0 and constants c1, 𝑐2 > 0 such that for all 𝑛 > 𝑛0, 0 ≤ 𝑐1 × 𝑔 𝑛 ≤ f 𝑛 ≤ 𝑐2 × 𝑔 𝑛 EECE 230 - Introduction to Computation and Programming [Figure 3.1 in “Introduction to Algorithms”, Cormen, Leriseron, Rivest, and Stein, 2009] I.5 Working with Theta Useful properties: • f(n)=Θ 𝑔(𝑛) ⇒ 𝑔 𝑛 = Θ 𝑓(𝑛) • Θ 𝑔1(𝑛) + Θ 𝑔2(𝑛) = EECE 230 - Introduction to Computation and Programming 𝑓1 𝑛 + 𝑓2 𝑛 for some 𝑓1 𝑛 = Θ 𝑔1(𝑛) and 𝑓2 𝑛 = Θ 𝑔2(𝑛) means I.5 Working with Theta (Continued) Useful properties: • f(n)=Θ 𝑔(𝑛) ⇒ 𝑔 𝑛 = Θ 𝑓(𝑛) • Θ 𝑔1(𝑛) + Θ 𝑔2(𝑛) = Θ 𝑔1 𝑛 + 𝑔2(𝑛) • Θ 𝑔1(𝑛) × Θ 𝑔2(𝑛) = EECE 230 - Introduction to Computation and Programming I.5 Working with Theta (Continued) Useful properties: • f(n)=Θ 𝑔(𝑛) ⇒ 𝑔 𝑛 = Θ 𝑓(𝑛) • Θ 𝑔1(𝑛) + Θ 𝑔2(𝑛) = Θ 𝑔1 𝑛 + 𝑔2(𝑛) • Θ 𝑔1(𝑛) × Θ 𝑔2(𝑛) = Θ 𝑔1 𝑛 × 𝑔2(𝑛) EECE 230 - Introduction to Computation and Programming Examples: • Θ 1 + Θ 𝑛 = • Θ 𝑛 + Θ 𝑛 = • Θ 1 × 𝑛 = • Θ 𝑛 × 𝑛 = I.5 Working with Theta (Continued) Useful properties: • f(n)=Θ 𝑔(𝑛) ⇒ 𝑔 𝑛 = Θ 𝑓(𝑛) • Θ 𝑔1(𝑛) + Θ 𝑔2(𝑛) = Θ 𝑔1 𝑛 + 𝑔2(𝑛) • Θ 𝑔1(𝑛) × Θ 𝑔2(𝑛) = Θ 𝑔1 𝑛 × 𝑔2(𝑛) EECE 230 - Introduction to Computation and Programming Examples: • Θ 1 + Θ 𝑛 = Θ 𝑛 • Θ 𝑛 + Θ 𝑛 = Θ 𝑛 • Θ 1 × 𝑛 = Θ 𝑛 • Θ 𝑛 × 𝑛 = Θ 𝑛2 I.5 Working with Theta: linear Search running time (Continued) 𝑇 𝑛 = Θ 𝑛 steps EECE 230 - Introduction to Computation and Programming • Instead of using constants, use Θ notation • Worst case if e not in L • Worst case running time of linearSearch: • Note that indexing operator L[i] takes Θ 1 time: recall for the lists lectures that they are implemented using contiguous memory cells • Best case running time: I.5 Working with Theta: linear Search running time (Continued) 𝑇 𝑛 = Θ 𝑛 steps EECE 230 - Introduction to Computation and Programming • Instead of using constants, use Θ notation • Worst case if e not in L • Worst case running time of linearSearch: • Note that indexing operator L[i] takes Θ 1 time: recall for the lists lectures that they are implemented using contiguous memory cells • Best case running time: Θ 1 steps (if L[0] == e) I.5 Working with Theta: searching for two elements EECE 230 - Introduction to Computation and Programming • Worst case time: I.5 Working with Theta: searching for two elements (Continued) EECE 230 - Introduction to Computation and Programming • Worst case time: Θ 𝑛 +Θ 𝑛 +Θ 1 = Θ 𝑛 steps • Two sequential loops: Θ 𝑛 +Θ 𝑛 = Θ 𝑛 • Nesting loops costs more Θ 𝑛 Θ 𝑛 Passing parameters to function and return I.6 Time analysis of element distinctness function • From the lists lectures (function version): start with naive version • Worst case ? EECE 230 - Introduction to Computation and Programming I.6 Time analysis of element distinctness function (Continued) • From the lists lectures (function version): start with naive version • Worst case if all distinct • Inner loop takes Θ 𝑛 steps EECE 230 - Introduction to Computation and Programming Θ 𝑛 • Thus total worst case time of naiveDistinctElements is Θ 𝑛 + n × Θ 𝑛 = Θ 𝑛2 steps Control of outer for, passing parameters to function, final return I.6 Time analysis of element distinctness function (Continued) • From the lists lectures (function version): start with naive version • Worst case if all distinct • Inner loop takes Θ 𝑛 steps EECE 230 - Introduction to Computation and Programming Θ 𝑛 • Thus total worst case time of naiveDistinctElements is Θ 𝑛 + n × Θ 𝑛 = Θ 𝑛2 steps • Nested loops • Best case running time: I.6 Time analysis of element distinctness function (Continued) • From the lists lectures (function version): start with naive version • Worst case if all distinct • Inner loop takes Θ 𝑛 steps EECE 230 - Introduction to Computation and Programming Θ 𝑛 • Thus total worst case time of naiveDistinctElements is Θ 𝑛 + n × Θ 𝑛 = Θ 𝑛2 steps • Nested loops • Best case running time: Θ 1 (if L[0]==L[1]) I.6 Time analysis of element distinctness function (Continued) • Now consider less naive function: • Worst case? EECE 230 - Introduction to Computation and Programming I.6 Time analysis of element distinctness function (Continued) • Now consider less naive function: • Worst case if distinct, in which case inner loop takes Θ 𝑛 − 𝑖 steps EECE 230 - Introduction to Computation and Programming Θ 𝑛 − 𝑖 I.6 Time analysis of element distinctness function (Continued) • Now consider less naive function: • Worst case if distinct, in which case inner loop takes Θ 𝑛 − 𝑖 steps EECE 230 - Introduction to Computation and Programming Θ 𝑛 − 𝑖 • Therefore, worst case running time of distinctElements is 𝚯 𝐧𝟐 : T n = Θ 𝑛 + σ𝑖=0 𝑛−1 Θ 𝑛 − 𝑖 = Θ( σ𝑖=0 𝑛−1 𝑛 − 𝑖 ) = Θ n2 (since σ𝑖=0 𝑛−1 𝑛 − 𝑖 = 𝑛 + 𝑛 − 1 + ⋯ + 1 = 𝑛 𝑛+1 2 ) • That is, the speedup trick (𝑗 ≥ 𝑖 + 1) only changed T(n) by a constant I.7 Other asymptotic notations (Continued) Theta: f n = Θ g n f(n) is asymptotically like g(n) Big O: f n = O g n f(n) is asymptotically like g(n) or weaker than g(n) There exist c > 0 and 𝑛0 > 0 such that for all 𝑛 > 𝑛0, 0 ≤ 𝑓 𝑛 ≤ 𝑐 × 𝑔(𝑛) Little o: f n = o g n f(n) is asymptotically weaker than g(n) lim 𝑛→∞ 𝑓 𝑛 𝑔 𝑛 = 0 EECE 230 - Introduction to Computation and Programming • Note: f n = O g n and g n = O f n  f n = Θ g n • Notational difference compared to [Guttag]: • f = O g in [Guttag] means f = Θ g here • f ∈ O g in [Gutta] means f = O g here I.7 Other asymptotic notations (Continued) Theta: f n = Θ g n f(n) is asymptotically like g(n) Big O: f n = O g n f(n) is asymptotically like g(n) or weaker than g(n) There exist c > 0 and 𝑛0 > 0 such that for all 𝑛 > 𝑛0, 0 ≤ 𝑓 𝑛 ≤ 𝑐 × 𝑔(𝑛) Little o: f n = o g n f(n) is asymptotically weaker than g(n) lim 𝑛→∞ 𝑓 𝑛 𝑔 𝑛 = 0 EECE 230 - Introduction to Computation and Programming • Note: f n = O g n and g n = O f n  f n = Θ g n • Notational difference compared to [Guttag]: • f = O g in [Guttag] means f = Θ g here • f ∈ O g in [Gutta] means f = O g here I.7 Other asymptotic notations: examples (Continued) EECE 230 - Introduction to Computation and Programming • 5 × 𝑛2 + 1000 × 𝑛 + 17 = Θ 𝑛2 • 5 × 𝑛2 + 1000 × 𝑛 + 17 = O 𝑛2 • 5 × 𝑛2 + 1000 × 𝑛 + 17 ≠ o 𝑛2 • 5 × 𝑛2 + 1000 × 𝑛 + 17 ≠ Θ 𝑛3 • 5 × 𝑛2 + 1000 × 𝑛 + 17 = O n3 • 5 × 𝑛2 + 1000 × 𝑛 + 17 = o n3 • 5 × 𝑛2 + 1000 × 𝑛 + 17 ≠ Θ 𝑛 • 5 × 𝑛2 + 1000 × 𝑛 + 17 ≠ O 𝑛 • 5 × 𝑛2 + 1000 × 𝑛 + 17 ≠ o(𝑛) I.7 Other asymptotic notations: examples (Continued) EECE 230 - Introduction to Computation and Programming • 5 × 𝑛2 + 1000 × 𝑛 + 17 = Θ 𝑛2 • 5 × 𝑛2 + 1000 × 𝑛 + 17 = O 𝑛2 • 5 × 𝑛2 + 1000 × 𝑛 + 17 ≠ o 𝑛2 • 5 × 𝑛2 + 1000 × 𝑛 + 17 ≠ Θ 𝑛3 • 5 × 𝑛2 + 1000 × 𝑛 + 17 = O n3 • 5 × 𝑛2 + 1000 × 𝑛 + 17 = o n3 • 5 × 𝑛2 + 1000 × 𝑛 + 17 ≠ Θ 𝑛 • 5 × 𝑛2 + 1000 × 𝑛 + 17 ≠ O 𝑛 • 5 × 𝑛2 + 1000 × 𝑛 + 17 ≠ o(𝑛) I.7 Other asymptotic notations (Continued) EECE 230 - Introduction to Computation and Programming • Say that you have an algorithm with worst case running time T(n) • What does T(n) = Θ g n mean? The worst case running time grows like g(n), i.e., g(n) is an asymptotic worst case guarantee which is attainable. • What does T(n) = O g n mean? The worst case running time grows like g(n) or is weaker than g(n), i.e., g(n) is an asymptotic worst case guarantee which may or may not be attainable. • What does T(n) = o g n mean? The algorithm is asymptotically much faster than g(n) I.7 Other asymptotic notations (Continued) EECE 230 - Introduction to Computation and Programming • Say that you have an algorithm with worst case running time T(n) • What does T(n) = Θ g n mean? The worst case running time grows like g(n), i.e., g(n) is an asymptotic worst case guarantee which is attainable. • What does T(n) = O g n mean? The worst case running time grows like g(n) or is weaker than g(n), i.e., g(n) is an asymptotic worst case guarantee which may or may not be attainable. • What does T(n) = o g n mean? The algorithm is asymptotically much faster than g(n) I.8 Common growth rates • Θ(1) is called constant running time • Θ(log n ) is called logarithmic running time • Θ(n) is called linear running time • Θ(n log n ) is called log-linear running time • Θ n2 is called quadratic running time • Θ(nk),where 𝑘 > 0 is a constant, is called polynomial running time • Θ(𝑐𝑛), where c > 1 is a constant, is called exponential running time EECE 230 - Introduction to Computation and Programming I.9 Comparison of common growth rates EECE 230 - Introduction to Computation and Programming [Guttag, 2016, Chapter 9] I.9 Comparison of common growth rates (Continued) EECE 230 - Introduction to Computation and Programming [Guttag, 2016, Chapter 9] I.9 Comparison of common growth rates (Continued) EECE 230 - Introduction to Computation and Programming [Guttag, 2016, Chapter 9] I.10 Examples from Programing Assignments (PA) 1 and 2 (Continued) • [PA1.Problem 4] Quadratic equations solver: Θ 1 time • [PA2.Problem 1.a] Time to find the factorial of a given number n: Θ n artithmetic operations (for large n, multiplications and additions cost more than Θ 1 time) • [PA2.Problem 2] Time to find the max in a sequence of 𝑛 number entered by user: Θ n time Space (memory): Θ 1 • [PA2.Problem 3.a] Time to check if a given number n is prime: Θ √n time (best known poly-log: Θ log 𝑛 𝑐 , where c > 0 is a constant) EECE 230 - Introduction to Computation and Programming I.10 Examples from Programing Assignments (PA) 1 and 2 (Continued) • [PA1.Problem 4] Quadratic equations solver: Θ 1 time • [PA2.Problem 1.a] Time to find the factorial of a given number n: Θ n arithmetic operations (for large n, multiplications and additions cost more than Θ 1 time) • [PA2.Problem 2] Time to find the max in a sequence of 𝑛 number entered by user: Θ n time Space (memory): Θ 1 • [PA2.Problem 3.a] Time to check if a given number n is prime: Θ √n arithmetic operations (best known poly-log: Θ log 𝑛 𝑐 , where c > 0 is a constant) EECE 230 - Introduction to Computation and Programming I.10 Examples from Programing Assignment (PA) 2 (Continued) • [PA2.Problem 4.a] Time to check if a given number n is square: Θ √n time • [PA2.Problem 4.b] Time to check if a given number n is square using bisection method (function version): • Θ log 𝑛 arithmetic operation • Why? EECE 230 - Introduction to Computation and Programming I.10 Examples from Programing Assignment (PA) 2 (Continued) • [PA2.Problem 4.a] Time to check if a given number n is square: Θ √n arithmetic operations • [PA2.Problem 4.b] Time to check if a given number n is square using bisection method (function version): • Θ log 𝑛 arithmetic operations • Why? EECE 230 - Introduction to Computation and Programming I.11 Time analysis of square-root test using bisection • Initial search interval consists of the integers in [1, n] • After each iteration of the while loop, the length of the search interval is reduced by at least half • Thus after k iterations, its length is at most 𝐧/𝟐𝐤 • Hence after at most 𝐥𝐨𝐠𝟐 𝐧 iterations, its length is at most 1 • Moreover, it is reduced by at least one integer at each iteration (as either 𝐥𝐨𝐰 is set to 𝐦𝐢𝐝 + 𝟏 or 𝐡𝐢𝐠𝐡 to 𝐦𝐢𝐝 − 𝟏 ,if 𝐦𝐢𝐝 × 𝐦𝐢𝐝 ≠ 𝐧 ) • Hence after at most 𝐥𝐨𝐠𝟐 𝐧 + 𝟏 iterations, its must be empty • Thus, the worst case time: 𝐎( 𝐥𝐨𝐠𝟐 𝐧 + 𝟏) = 𝐎 𝐥𝐨𝐠 𝐧 arithmetic operation (Big O in Section I.7 above) • It is actually 𝚯 𝐥𝐨𝐠 𝐧 : worst case when n is not square EECE 230 - Introduction to Computation and Programming II •Binary Search •Insertion Sort EECE 230 - Introduction to Computation and Programming II.1 Binary Search: the problem of searching sorted lists • When we have many search queries, it is more efficient to first sort the list and implement the search queries using a searching algorithm smarter than linear search, which takes linear time • Given a list L[0…n-1] of integers sorted in non-decreasing order and a number x, check if x is in L: if found return an index i such that L[i]= x, otherwise return -1 EECE 230 - Introduction to Computation and Programming II.1 Idea of Binary Search • Same as the bisection method • Compare x with the middle element of L • If >, we can ignore the lower half of L since L is sorted • If <, we can ignore the upper half of L since L is sorted • If =, we are done (x is an element of L) • Repeat EECE 230 - Introduction to Computation and Programming II.1 Try it on a example Try it on: a. L = [-3,-2,1,1,2,3, 5, 6, 8, 9,17] and x = 5 b. Same L with and x = 4 EECE 230 - Introduction to Computation and Programming EECE 230C - Introduction to Computation and Programming [-3,-2,1,1,2,3, 5, 6, 8, 9,17] II.1.a Binary search for 5 in [-3,-2,1,1,2,3, 5, 6, 8, 9,17] 0 1 2 3 4 5 6 7 8 9 10 EECE 230C - Introduction to Computation and Programming [-3,-2,1,1,2,3, 5, 6, 8, 9,17] II.1.a Binary search for 5 in [-3,-2,1,1,2,3, 5, 6, 8, 9,17] 0 1 2 3 4 5 6 7 8 9 10 EECE 230C - Introduction to Computation and Programming [-3,-2,1,1,2,3, 5, 6, 8, 9,17] [5, 6, 8, 9,17] II.1.a Binary search for 5 in [-3,-2,1,1,2,3, 5, 6, 8, 9,17] 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 Return the index 6 of 5 EECE 230C - Introduction to Computation and Programming [-3,-2,1,1,2,3, 5, 6, 8, 9,17] [5, 6, 8, 9,17] [5, 6] II.1.a Binary search for 5 in [-3,-2,1,1,2,3, 5, 6, 8, 9,17] 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 Return the index 6 of 5 EECE 230C - Introduction to Computation and Programming [-3,-2,1,1,2,3, 5, 6, 8, 9,17] [5, 6, 8, 9,17] [5, 6] II.1.a Binary search for 5 in [-3,-2,1,1,2,3, 5, 6, 8, 9,17] 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 Return the index 6 of 5 EECE 230C - Introduction to Computation and Programming [-3,-2,1,1,2,3, 5, 6, 8, 9,17] II.1.b Binary search for 4 in [-3,-2,1,1,2,3, 5, 6, 8, 9,17] 0 1 2 3 4 5 6 7 8 9 10 EECE 230C - Introduction to Computation and Programming [-3,-2,1,1,2,3, 5, 6, 8, 9,17] II.1.b Binary search for 4 in [-3,-2,1,1,2,3, 5, 6, 8, 9,17] 0 1 2 3 4 5 6 7 8 9 10 EECE 230C - Introduction to Computation and Programming [-3,-2,1,1,2,3, 5, 6, 8, 9,17] [5, 6, 8, 9,17] II.1.b Binary search for 4 in [-3,-2,1,1,2,3, 5, 6, 8, 9,17] 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 EECE 230C - Introduction to Computation and Programming [-3,-2,1,1,2,3, 5, 6, 8, 9,17] [5, 6, 8, 9,17] [5, 6] II.1.b Binary search for 4 in [-3,-2,1,1,2,3, 5, 6, 8, 9,17] 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 EECE 230C - Introduction to Computation and Programming [-3,-2,1,1,2,3, 5, 6, 8, 9,17] [5, 6, 8, 9,17] [5, 6] [] II.1.b Binary search for 4 in [-3,-2,1,1,2,3, 5, 6, 8, 9,17] 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 EECE 230C - Introduction to Computation and Programming [-3,-2,1,1,2,3, 5, 6, 8, 9,17] [5, 6, 8, 9,17] [5, 6] [] II.1.b Binary search for 4 in [-3,-2,1,1,2,3, 5, 6, 8, 9,17] 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 Empty search interval: return -1 II.1 Elaborate on idea • We need 3 variables: low, mid, and high • Initially: low = 0 and high = n-1 • Compute: mid = (n-1)//2 (floor of (n-1)/2, i.e., largest integer less than or equal to (n-1)/2) • If x==A[mid], done: return mid • If L[mid]<x, update low = mid +1 and keep high the same • If L[mid]>x, update high = mid -1 and keep low the same • Re-compute: mid = (low+high)//2 • Repeat this process until either x is found or low > high, in which case return -1 EECE 230 - Introduction to Computation and Programming II.1 Binary Search function EECE 230 - Introduction to Computation and Programming