Constructing and Tracing Algorithms for Linear and Binary Search
Linear Search: A Simple Yet Powerful Approach
- Initialize a variable foundIndex to -1 to indicate that the target has not been found.
- Iterate through each element in the list:
- If the current element matches the target, update foundIndex to the current index and break the loop.
- Return foundIndex. If it remains -1, the target is not in the list.
Tip
- When choosing a search algorithm, always consider whether the data is sorted.
- Binary search is only effective on sorted datasets.
Practical Applications of Search Algorithms
- Linear Search:
- Searching an unsorted list of items in a game inventory
- Finding a specific word in a document
- Binary Search:
- Looking up a phone number in a sorted directory
- Searching for a product in a sorted online catalog
Note
- Binary search requires the data to be sorted.
- If the dataset is frequently updated, the cost of sorting may outweigh the benefits of binary search.
Example
Tracing Algorithms: A Step-by-Step Approach
Linear Search:
- Input: ["The Old Bridge", "Down by the Fountain", "Super Searchin'", "Little Red Lies", "Geescht", "Watching Over You"]
- Target: "Little Red Lies"
- Trace:
- Compare "The Old Bridge" with "Little Red Lies": No match
- Compare "Down by the Fountain" with "Little Red Lies": No match
- Compare "Super Searchin'" with "Little Red Lies": No match
- Compare "Little Red Lies" with "Little Red Lies": Match found at index 3
Binary Search:
- Input: [10, 11, 12, 15, 20, 25, 45, 84, 129, 139, 483, 586, 685]
- Target: 139
- Trace:
- Calculate midpoint: Index 6 (value 45)
- 139 & gt, 45, move left to index 7
- Calculate midpoint: Index 9 (value 139)
- Match found at index 9
Self review
- What are the key differences between linear and binary search algorithms?
- How does the efficiency of binary search change if the data is not sorted?
- Can you think of a scenario where linear search might be more appropriate than binary search?
