Linear Search in Python
Introduction to Linear Search in Python
Linear search in Python is a simple and straightforward searching algorithm used to find a specific element in a list or array. Enhance your search procedures utilizing the linear search algorithm in Python.
Acquire comprehensive knowledge about step-by-step implementation of linear search in Python, grasp its fundamental principles and diverse applications.
What is Searching Technique?
Searching, in the context of computer science, refers to the process of locating a specific element, value, or data within a collection, such as an array, list, or database.
In Python, searching can be categorized into two main types:
- Linear Search
- Binary Search
What is Linear Search in Python?
What is Linear Search with Example?
The following steps are followed for finding element k = 2 from the given array :
1. Start from the first element and traverse to the last. Here k=2 and each element is x.
2. If found(k==x); return the index.
3. Else, not found.
Linear Search Algorithm
Here’s how the Linear Search algorithm works:
Start at the beginning of the collection (usually at index 0).
Compare the target element you’re looking for with the current element in the collection.
If the current element matches the target element, the search is successful, and the algorithm returns the index of the current element.
If there’s no match, move to the next element in the collection and repeat steps 2-3.
Continue this process until you find the target element or reach the end of the collection.
If you reach the end of the collection without finding the target element, the algorithm returns a special value (commonly -1) to indicate that the element was not found.
def linear_search(arr, target):
for index, value in enumerate(arr):
if value == target:
return index
return -1
my_list = [10, 3, 7, 1, 9, 5]
target_value = 7
result = linear_search(my_list, target_value)
if result != -1:
print(f"Target {target_value} found at index {result}")
else:
print("Target not found in the list")
Output: Target 7 found at index 2
Explanation :
In summary, the linear search algorithm iterates through the list to find the target value. In this specific case, the target value 7 is found at index 2 in the list, as indicated by the output.
Linear Search in Python using List
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i
return -1
my_list = [10, 4, 7, 2, 8, 5]
target_element = 7
result = linear_search(my_list, target_element)
if result != -1:
print("Element", target_element, "found at index", result)
else:
print("Element", target_element, "not found in the list")
Output: Element 7 found at index 2
Explanation :
The code defines a linear_search function that searches for a target element in a list using a linear search algorithm. If found, it returns the index; otherwise, it returns -1. The example uses this function to search for the element 7 in the list and prints a message indicating whether it was found or not.
Linear Search in Python using for loop
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i
return -1
my_list = [10, 4, 7, 2, 8, 5]
target_element = 7
result = linear_search(my_list, target_element)
if result != -1:
print("Element", target_element, "found at index", result)
else:
print("Element", target_element, "not found in the list")
Output: Element 7 found at index 2
Explanation :
The code defines a linear_search function to find a target element in a list using a for loop. It iterates through the list, comparing each element with the target. If found, it returns the index; otherwise, it returns -1. The program then uses this function to search for element 7 in the list and prints a message indicating whether it was found or not. In this case, it finds the element at index 2 and prints the result accordingly.
Linear Search in Python without using function
my_list = [10, 4, 7, 2, 8, 5]
target_element = 7
found = False
for i in range(len(my_list)):
if my_list[i] == target_element:
found = True
index = i
break
if found:
print("Element", target_element, "found at index", index)
else:
print("Element", target_element, "not found in the list")
Output: Element 7 found at index 2
Explanation :
This code performs a linear search without using a function. It iterates through the list, comparing each element to the target (7). If found, it sets the found flag to True, records the index, and breaks out of the loop. Then, it prints a message indicating whether the element was found or not. In this case, it finds the element at index 2 and prints the result accordingly.
Linear Search in Python using Recursion
def linear_search(arr, target, index=0):
if index >= len(arr):
return -1
if arr[index] == target:
return index
return linear_search(arr, target, index + 1)
my_list = [10, 4, 7, 2, 8, 5]
target_element = 7
result = linear_search(my_list, target_element)
if result != -1:
print("Element", target_element, "found at index", result)
else:
print("Element", target_element, "not found in the list")
Output: Element 7 found at index 2
Explanation :
This code defines a linear_search function that uses recursion to search for a target element (7) in a list. It compares each element with the target and increments the index until the target is found or the end of the list is reached. The program then prints a message indicating whether the element was found or not. In this case, it finds the element at index 2 and prints the result accordingly.
Linear Search in Python using Recursion
Time Complexity for Linear Search
The time complexity of the linear search algorithm in Python is O(n), where “n” represents the number of elements in the list or array being searched. This means that as the size of the list grows, the time taken for the linear search also grows linearly.
There are mainly three case for Time complexity :
- Best Case : O(1)
- Average Case : O(n)
- Worst Case : O(n)
Conclusion
The linear search in Python algorithm is well-suited for modestly sized lists (up to 100 elements) due to its examination of every element in pursuit of the sought-after value. In scenarios involving larger lists, such as a list of 10,000 elements with the target value situated at the concluding position, the process becomes time-consuming as each element necessitates comparison.
To expedite results, the binary search algorithm presents an alternative.
The fundamental principles of linear search have been elucidated. In the forthcoming tutorial, we will delve into the second and widely acclaimed searching algorithm known as Binary Search.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Question 1.
What is linear search, and when is it used?
Linear search, also known as sequential search, is a basic algorithm that sequentially examines each element in a list to find a specific value. It’s used when the list is small or unsorted, and its simplicity allows for straightforward implementation.
Question 2.
How does linear search work in Python?
Linear search iterates through each element of a list and compares it with the target value. If a match is found, the index of the matching element is returned. If the entire list is searched without finding a match, -1 is returned.
Question 3.
What’s the time complexity of linear search?
The time complexity of linear search is O(n), where “n” is the number of elements in the list. It grows linearly with the size of the list, making it less efficient for larger datasets.
Question 4.
When should I use linear search?
Linear search is suitable for small lists or when the list is unsorted. It’s a good choice when the dataset is limited or when sorting the list might be more time-consuming than performing a linear search.
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment