Computer Science 1037A/B Lecture Notes - Lecture 3: Linear Search, Binary Search Algorithm, Dynamic Array
Document Summary
Searching is the process of looking for a specific element (in an array) Example: discovering whether a certain score is included in a list of scores. Searching is a common task in computer programming. There are many algorithms and data structures devoted to searching. In this section, two commonly used approaches are discussed, linear search and binary search. The linear search approach compares the key element, key, sequentially with each element in the array list. The function continues to do so until the key matches an element in the list or the list is exhausted without a match being found. If a match is made, the linear search returns the index of the element in the array that matches the key. If no match is found, the search returns -1. For binary search to work, the elements in the array must already be ordered. Without loss of generality, assume that the array is in ascending order.