Linear Search Flashcards
Gives two reasons why searching important in computing?
- It is a fundamental operation in computing that involves finding a specific item or value from a collection of data
- It plays a crucial role in various applications and is essential for efficient data retrieval and information processing
What is searching?
Data come in large amounts, typically unsorted or random
We often need to locate an item (strings, numbers, lists…) in a dataset
Searching is the process of locating a particular element or record within a given dataset
It involves examining the data systematically to determine if the desired item exists and, if so, its location or other relevant information
What are the two types of search algorithms?
- Linear Search: Sequentially checks each element until a match is found or the end of the collection is reached
- Binary Search: Efficiently searches sorted collections by repeatedly dividing the search space in half
What is linear (sequential) search?
It is a simple searching algorithm that sequentially checks each element in a list or array until a match is found or the end of the list is reached
It starts at the beginning of the list and checks each element in order until the target value is found OR the end of the list is reached
Why is linear search also called a “sequential search”?
Because it examines elements in a linear order, one by one
What is the algorithm for it? (5 steps)
- Start at the first element of the list
- Compare the current element with the target element
- If a match is found, return the index of the element
- If the end of the list is reached without finding a match, return a special value (e.g., -1) to indicate the element was not found
- If a match is not found, move to the next element and repeat steps 2-5
What does this mean?
Linear_search(arr, target)
This takes an array (list) and a target element as parameters
It iterates through each element of the array using a for loop and compares each element with the target
If a match is found,
= the function returns the index of the element
If the loop **completes without finding a match*
= the function returns -1 to indicate that the element was not found
Given the list:
[0, 11, 4, 7, 5, 1, 8, 3, 6]
How many loop iterations is does the code need to complete to find?
Value 0?
Value 11?
Value 4?
Value 2?
NOTE: you do this the same way but backwards for reverse order searching
Value 0 = 1
Value 11 = 2
Value 4 = 3
Value 2 = 9
What would be the benefit of searching backwards in the list (starting from the last element and moving towards the first element)
- Reverse order requirement:
- When the desired order of search results is from
the last occurrence to the first occurrence
Ex. identifying the most recent entries in a log. - Optimized search:
- If you have prior knowledge or an expectation that the target value is more likely to be found towards the end of the list
= searching backwards can potentially lead to faster results
Ex. With “for” loop:
def linear_search_backwards(arr, target):
for i in range(len(arr) - 1, -1, -1):
if arr[i] == target:
return i
return -1
What happens when multiple occurrences occur?
You can use this to identify all the indexes where
a specific item occurs in a list
Return a list of indexes where multiple occurrences of an item are found
This algorithm provides a useful tool for tasks such as counting occurrences, filtering data, or identifying patterns
What is the algorithm involved in multiple occurrences? (4 steps)
- Initialize an empty list called “occurrences” to store the indexes of the found occurrences
- Iterate through each element in the list
- If the current element matches the target item:
= Append the index of the current element to the “occurrences” list. - After iterating through the entire list, return the “occurrences” list
What is the algorithm involved in multiple occurrences? (4 steps)
The given list is [2, 4, 7, 4, 2, 9, 4, 1, 8, 3, 4].
We are searching for occurrences of the target item 4
What would be the result?
NOTE: this would also look the same for if you found multiple occurrences backwards
= it would just be in reverse order (from last element to the first element)
The algorithm iterates through the list and finds four occurrences of 4
= at indexes 1, 3, 6, and 10
The algorithm returns the list [1, 3, 6, 10] as the indexes where the target item 4 occurred
Linear search may not be efficient for “______” or “_______” lists
Large; sorted
