DOC PREVIEW
CMU CS 15122 - Lecture Notes

This preview shows page 1-2-3-4 out of 12 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

IntroductionBinary SearchImplementing Binary SearchOne More ObservationBig-O NotationSome MeasurementsLecture Notes onBinary Search15-122: Principles of Imperative ComputationFrank PfenningLecture 6January 27, 20111 IntroductionOne of the fundamental and recurring problems in computer science is tofind elements in collections, such as elements in sets. An important algo-rithm for this problem is binary search. We use binary search for an integerin a sorted array to exemplify it. We started in the last lecture by discussinglinear search and giving some background on the problem.We will also once again see the importance of loop invariants in writingcorrect code. Here is a note by Jon Bentley about binary search:I’ve assigned [binary search] in courses at Bell Labs and IBM. Profes-sional programmers had a couple of hours to convert [its] descriptioninto a program in the language of their choice; a high-level pseudocodewas fine. At the end of the specified time, almost all the programmersreported that they had correct code for the task. We would then takethirty minutes to examine their code, which the programmers did withtest cases. In several classes and with over a hundred programmers,the results varied little: ninety percent of the programmers found bugsin their programs (and I wasn’t always convinced of the correctness ofthe code in which no bugs were found).I was amazed: given ample time, only about ten percent of profes-sional programmers were able to get this small program right. Butthey aren’t the only ones to find this task difficult: in the history inSection 6.2.1 of his Sorting and Searching, Knuth points out thatLECTURE NOTES JANUARY 27, 2011Binary Search L6.2while the first binary search was published in 1946, the first publishedbinary search without bugs did not appear until 1962.—Jon Bentley, Programming Pearls (1st edition), pp.35–36I contend that what these programmers are missing is the understandingof how to use loop invariants in composing their programs. They helpus to make assumptions explicit and clarify the reasons why a particularprogram is correct. Part of the magic of pre- and post-conditions as well asloop invariants and assertions is that they localize reasoning. Rather thanhaving to look at the whole program, or the whole function, we can focuson individual statements tracking properties via the loop invariants andassertions.2 Binary SearchCan we do better than searching through the array linearly? If you don’tknow the answer already it might be surprising that, yes, we can do signif-icantly better! Perhaps almost equally surprising is that the code is almostas short!Before we write the code, let us describe the algorithm. We start byexamining the middle element of the array. If it smaller than x than x mustbe in the upper half of the array (if it is there at all); if is greater than x thenit must be in the lower half. Now we continue by restricting our attentionto either the upper or lower half, again finding the middle element andproceeding as before.We stop if we either find x, or if the size of the subarray shrinks to zero,in which case x cannot be in the array.Before we write a program to implement this algorithm, let us analyzethe running time. Assume for the moment that the size of the array is apower of 2, say 2k. Each time around the loop, when we examine the mid-dle element, we cut the size of the subarrays we look at in half. So before thefirst iteration the size of the subarray of interest is 2k. After the second iter-ation it is of size 2k−1, then 2k−2, etc. After k iterations it will be 2k−k= 1,so we stop after the next iteration. Altogether we can have at most k + 1iterations. Within each iteration, we perform a constant amount of work:computing the midpoint, and a few comparisons. So, overall, when givena size of array n we perform c ∗ log2(n) operations.11In general in computer science, we are mostly interested in logarithm to the base 2 sowe will just write log(n) for log to the base 2 from now on unless we are considering aLECTURE NOTES JANUARY 27, 2011Binary Search L6.3If the size n is not a power of 2, then we can round n up to the nextpower of 2, and the reasoning above still applies. For example, is n = 13we round it up to 16 = 24. The actual number of steps can only be smallerthan this bound, because some of the actual subintervals may be smallerthan the bound we obtained when rounding up n.The logarithm grows much slower than the linear function that we ob-tained when analyzing linear search. As before, consider that we are dou-bling the size of the input, n0= 2∗n. Then the number of operations will bec ∗ log(2 ∗ n) = c ∗ (log(2) + log(n)) = c ∗ (1 + log(n)) = c + c ∗ log(n). So thenumber of operations increases only by a constant amount c when we dou-ble the size of the input. Considering that the largest representable positivenumber in two’s complement representation is 231− 1 (about 2 billion) bi-nary search even for unreasonably large arrays will only traverse the loop31 times! So the maximal number of operations is effectively bounded by aconstant if it is logarithmic.different base.LECTURE NOTES JANUARY 27, 2011Binary Search L6.43 Implementing Binary SearchThe specification for binary search is the same as for linear search.int binsearch(int x, int[] A, int n)//@requires 0 <= n && n <= \length(A);//@requires is_sorted(A, n);/*@ensures (-1 == \result && !is_in(x, A, n))|| ((0 <= \result && \result < n) && A[\result] == x);@*/;We have two variables, lower and upper, which hold the lower and upperend of the subinterval in the array that we are considering. We start withlower as 0 and upper as n, so the interval includes lower and excludesupper. This often turns out to be a convenient choice when computingwith arrays.The for loop from linear search becomes a while loop, exiting whenthe interval has size zero, that is, lower == upper. We can easily write thefirst loop invariant, relating lower and upper to each other and the overallbound of the array.int binsearch(int x, int[] A, int n)//@requires 0 <= n && n <= \length(A);//@requires is_sorted(A,n);/*@ensures (-1 == \result && !is_in(x, A, n))|| ((0 <= \result && \result < n) && A[\result] == x);@*/{ int lower = 0;int upper = n;while (lower < upper)//@loop_invariant 0 <= lower && lower <= upper && upper <= n;{// ...??...}return -1;}In the body of the loop, we first compute the midpoint mid. We assertthat the midpoint is indeed between


View Full Document

CMU CS 15122 - Lecture Notes

Download Lecture Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?