Lecture 4 Search PDF

Lecture 4 Search 15-122: Principles of Imperative Computation (Fall 2024) Frank Pfenning One of the fundamental and recurring problems in computer science is to find elements in collections, such a...

Lecture 4 Search 15-122: Principles of Imperative Computation (Fall 2024) Frank Pfenning One of the fundamental and recurring problems in computer science is to find elements in collections, such as elements in sets. An important algo- rithm for this problem is binary search. We use binary search for an integer in a sorted array to exemplify it. As a preliminary study in this lecture we analyze linear search, which is simpler, but not nearly as efficient. Still it is often used when the requirements for binary search are not satisfied, for example, when the elements we have to search are not arranged in a sorted array. Additional Resources Review slides (https://cs.cmu.edu/~15122/handouts/slides/review/04-linsearch. pdf) OLI modules (https://cs.cmu.edu/~15122/handouts/oli/04.shtml) Code for this lecture (https://cs.cmu.edu/~15122/handouts/code/04-linsearch. tgz) In term of our learning goals, we address the following: Computational Thinking: Developing contracts (pre- and post-conditions, assertions, and loop invariants) that establish the safety and correct- ness of imperative programs. Evaluating the use of order (sorted data) as a problem-solving tool. Identifying the difference between specification and implementation. Algorithms and Data Structures: Describing linear search. Programming: We will practice deliberate programming together in lectures. Furthermore, identifying, describing, and effectively using short-circuiting Boolean operators will play an important role. L ECTURE N OTES c Carnegie Mellon University 2024  Lecture 4: Search 2 1 Linear Search in an Unsorted Array If we are given an array of integers A without any further information and have to decide if an element x is in A, we just have to search through it, element by element. We return true as soon as we find an element that equals x, false if no such element can be found. 1 bool is_in(int x, int[] A, int lo, int hi) 2 //@requires 0