01:198:107 Lecture Notes - Lecture 13: Linear Search, Binary Search Algorithm
5 Mar 2018
School
Department
Course
Professor
Document Summary
In an ordered array, one test can rule out a whole region of the array. Low: lowest index where the target might be. High: highest index where the target might be. Mid: where to look next, average of high and low. % assumes vector is in increasing order. % returns index j such that vector(j)==target. % returns 0 if target not in vector. To search a sorted array of length n, At most log(n) elements need to be looked at. For a large array binary search is faster than linear search. Not if the target is in the first element of the vector. We would like to make general statements about one algorithm being faster than another. Binary search is faster than linear search. There are too many variables to use variables to use actual time to compare algorithms. Count should model work done by algorithm. Problem: number of operations depends on size of input.
