CMPT 125 Lecture Notes - Lecture 7: Binary Logarithm, Linear Search, Artery Recordings
18 Dec 2018
School
Department
Course
Professor
Document Summary
If we do not know how the elements are arranged in the array, we can use a linear search (for loop), and go over all elements in the array one after another. In the worst case, the element we are looking for may be the last element in the array, or may not be in the array. (length of array when searching for an element in an unsorted array. ) Therefore, if the array contains n elements, the running time of the search is linear- o(n). If the array is sorted, then searching for an element in the array becomes easier. Divide: cut the array into 2 roughly equal pieces. Use the fact that the array is sorted: search in only one of the pieces. Running time for array of length n: denote the running time by t(n) Output: index of the element in the array (or n/a: compute the midpoint of the array, if array[midpoint] == element.
