DSA Linear Search
Linear Search
The linear search algorithm retrieves the index of the value it is looking for after searching through an array.
------ IMAGE MUKAVI -----
To observe how the Linear Search algorithm functions, run the simulation shown above.
Try finding value 5 to see what occurs when a value is not found.
This method is quite basic, making it simple to comprehend and use.
It is preferable to use the considerably quicker Binary Search algorithm—which we will discuss on the following page—if the array has already been sorted.
Sorting algorithms alter the array, but searching algorithms do not; this is a significant distinction between the two types of algorithms.
How it works:
1.Start by going over each value in the array one by one.
2.To see if any value matches the desired value, compare them all.
3.Return the value’s index if the value can be located.
4.Return -1 to indicate that the value was not found if the array’s end is reached and the value is not found.
Manual Run Through
Before we really implement Linear Search in a computer language, let’s attempt doing the searching manually to gain even more insight into how it functions. We are going to look for value 11.
Step 1: An array of random values is where we begin.
[ 12, 8, 9, 11, 5, 11]
Step 2: Do the first and second values in the array add up to 11?
[ 12, 8, 9, 11, 5, 11]
Step 3: The value at index 1 is the next one, and we compare it to 11 to determine if they are equivalent.
[ 12, 8, 9, 11, 5, 11]
Step 4: At index 2, we examine the subsequent value.
[ 12, 8, 9, 11, 5, 11]
Step 5: At index 3, we go on to the following value. Does it add up to eleven?
[ 12, 8, 9, 11, 5, 11]
We’ve located it!
You can find value 11 at index 3.
index position three is returned.
The linear search is complete.
The following steps can be seen animated by running the simulation:
------ IMAGE MUKAVI -----
Manual Run Through: What Happened?
This algorithm is quite simple to understand.
We begin by checking each item in the array to see whether it equals the value we are looking for, which is 11.
The value is returned and the index where it was found is returned when the value is found, ending the search.
In the event that the value cannot be found after searching the array, -1 is returned.
Linear Search Implementation
In order to apply the Linear Search method, we require:
- An array containing values to look up.
- a desired outcome to look for.
- a loop that traverses the array from beginning to end.
- An if-statement that, upon finding the target value, returns the current index and compares the current value with the target value.
- Return -1 at the end of the loop as we now know the target value has not been located.
This is how the Linear Search code appears when it is generated:
Example
def linearSearch(arr, targetVal):
for i in range(len(arr)):
if arr[i] == targetVal:
return i
return -1
arr = [3, 7, 2, 9, 5]
targetVal = 9
result = linearSearch(arr, targetVal)
if result != -1:
print("Value",targetVal,"found at index",result)
else:
print("Value",targetVal,"not found")
Linear Search Time Complexity
See this article for a broad description of time complexity.
See this page for a more comprehensive and in-depth discussion of Insertion Sort time complexity
If the target value is discovered using Linear Search to be the first array value in an array with n values, a single comparison is sufficient.
However, if Linear Search traverses the entire array of n values, failing to locate the desired value, n Comparisons are required.
This indicates that Linear Search’s time complexity is
O(n)
If we draw how much time Linear Search needs to find a value in an array of n values, we get this graph:
See how many comparisons are required for Linear Search to locate a value in an array of n values by running the simulation below for varying array sizes:
------ IMAGE MUKAVI -----
In the scenario above, selecting “Random,” “Descending,” or “Ascending” has no bearing on how quickly Linear Search operates.
