ACO 101 Final: Binary search. Analysis of running time. Recursive version of binary search
Document Summary
1 example: computing the intersection of two lists of students. In lecture 2, we started discussing the problem of computing the number of common elements in two arrays. We described an algorithm which loops over the two arrays and computes this in time. O(mn), where m and n are the sizes of the two arrays. The answer is yes, by using an algorithm called binary search. The basic idea is to look at the middle of the array. If we found the name (or student id) we searched for, we are done. Otherwise, we look to the right or left part of the array, depending on whether we have a name that occurs before or after the one in the middle, in terms of alphabetic order (or whatever ordering we have). The pseudocode for binary search in general is as follows: Inputs: a sorted array a of n elements, and a value val that we want to nd.
