CSE 100 Lecture 38: Chapter 9
Chapter 9
(*not on exam 3*)
● 9.1 Introduction to Search Algorithms
○ search: to locate a specific item in a list (array, vector, etc.) of information
○ two algorithms (methods) considered here:
■ linear search (also called Sequential Search)
■ Binary search
● Linear Search Algorithm
○ Set found to false
○ Set position to -1
○ Set index to 0
○ While index < number of elts and found is false
■ If list [index] is equal to search value
● found = true
● position = index
● End If
● Add 1 to index
● End While
● Return position
● Array numlist contains
○ [17, 23, 5, 11, 2, 29, 3]
○ Searching for the value 11, linear search examines 15, 23, 5, and 11
○ Searching for the value 7, linear search examines 17, 23, 5, 11, 2, 29, and 3
■ could not find
○ Linear Search
■ Benefits:
● easy algorithm to understand and to implement
● Elements in array can be in any order
■ Disadvantage
● inefficient (slow): for array of N elements, it examines N/2
elements on average for a value that is found in the array, N
elements for a value that is not in the array
○ Binary Search
■ 1. Examine the value of the middle element
■ 2. If the middle element has the desired value, done. Otherwise,
determine which half of the array may have the desired value. Continue
working with this portion of the array.
■ 3. Repeat steps 1 and 2 until either the element with the desired value is
found or there are no more elements to examine
■ Example →
● Array numlist2 contains
○ [2, 3, 5, 11, 17, 23, 29]
Document Summary
Search: to locate a specific item in a list (array, vector, etc. ) of information. While index < number of elts and found is false. If list [index] is equal to search value. [17, 23, 5, 11, 2, 29, 3] Searching for the value 11, linear search examines 15, 23, 5, and 11. Searching for the value 7, linear search examines 17, 23, 5, 11, 2, 29, and 3. Easy algorithm to understand and to implement. Elements in array can be in any order. Inefficient (slow): for array of n elements, it examines n/2 elements on average for a value that is found in the array, n elements for a value that is not in the array. If the middle element has the desired value, done. Otherwise, determine which half of the array may have the desired value. Continue working with this portion of the array.