Linear search, also known as sequential search, is a simple search algorithm. It sequentially checks each element in a list until a match is found or the entire list has been searched.
Algorithm:
- Start from the beginning of the list and examine each element one by one.
- Compare each element with the target value.
- If a match is found, return the index of the element.
- If the entire list is searched and no match is found, return -1.
Time Complexity: ^ The time complexity of linear search is O(n), where n is the number of elements in the list.
- In the worst-case scenario, the algorithm may need to traverse the entire list.
Advantages:
- Simple and easy to understand.
- Works well for small lists or unsorted lists.
Disadvantages:
- Inefficient for large lists or datasets.
- Not suitable for situations where a quick search is crucial.
Implementation in Python:
- Typically implemented using a loop (e.g., for or while) to iterate through the list.
- A function can be created to encapsulate the linear search logic, providing modularity and reusability.
Use Cases:
- Useful when the list is small, and efficiency is not a primary concern.
- Applicable when the list is unordered or partially ordered.
*Comparison with Other Search Algorithms:
- Linear search is less efficient than binary search for large sorted lists.
- Binary search has a time complexity of O(log n) but requires a sorted list.
Conclusion:
- Linear search is a straightforward algorithm suitable for basic search requirements.
- Its simplicity comes at the cost of efficiency, making it less suitable for large datasets or time-sensitive applications.
Program
# Accept a list from the user
my_list = [int(x) for x in input("Enter a list of numbers separated by spaces: ").split()]
# Accept the target value from the user
target_value = int(input("Enter the target value to search for: "))
# Perform linear search
found = False
for i in range(len(my_list)):
if my_list[i] == target_value:
found = True
index = i
break
# Display the result
if found:
print(f"Target {target_value} found at index {index}.")
else:
print(f"Target {target_value} not found in the list.")
Explanation:
Accepting User Input:
- The program starts by prompting the user to enter a list of numbers separated by spaces using the input function.
- The entered string is then split into individual numbers, converted to integers, and stored in the my_list variable.
Accepting Target Value:
- The program prompts the user to enter the target value to search for using the input function.
- The entered value is converted to an integer and stored in the target_value variable.
Linear Search:
- The program uses a for loop to iterate through each element in the list (my_list).
- Inside the loop, it checks if the current element is equal to the target value (target_value).
- If a match is found, it sets the found flag to True, records the index (i), and breaks out of the loop.
Displaying Result:
Finally, the program checks the found flag.
- If found is True, it prints a message indicating that the target value was found and displays the index.
- If found is False, it prints a message indicating that the target value was not found in the list.
my_list = [int(x) for x in input("Enter a list of numbers separated by spaces: ").split()]
- input("Enter a list of numbers separated by spaces: "): This part of the code prompts the user to enter a string of numbers separated by spaces. The input() function takes user input as a string.
- .split(): The split() method is used to split the entered string into a list of substrings. By default, it splits the string based on spaces.
- int(x) for x in ...: This is a list comprehension. It iterates over each substring (x) obtained after the split and converts it to an integer using int(x).
- my_list = [...]: The result of the list comprehension is assigned to the variable my_list. This variable now holds a list of integers created from the user's input.
Example
Suppose the user enters: 10 20 30 40
- The input() function captures the string "10 20 30 40".
- The .split() method splits this string into a list of substrings: ["10", "20", "30", "40"].
- The list comprehension iterates over each substring, converting it to an integer: [10, 20, 30, 40].
- The final list [10, 20, 30, 40] is assigned to the variable my_list.
