CSE 100 Lecture 38: Chapter 9

83 views3 pages
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]
Unlock document

This preview shows page 1 of the document.
Unlock all 3 pages and 3 million more documents.

Already have an account? Log in

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.

Get access

Grade+20% off
$8 USD/m$10 USD/m
Billed $96 USD annually
Grade+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
40 Verified Answers
Class+
$8 USD/m
Billed $96 USD annually
Class+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
30 Verified Answers

Related Documents

Related Questions