What is linear search
Linear search is looking for a target item in an array. Linear search returns the index of the target if found. Linear search will raise and exception if not found.
Algorithm
-
Iterate through entire array by index
- Get value at the index
- if value equals our target, return the index
-
If iteration completes without finding the target, raise an exception
Example
Complexity
| cases | complexity | description |
|---|---|---|
| best case | O(1) | target is the first item |
| average case | O(n) | target is the middle element |
| worst case | O(n) | target is not found |
Example: String Search Algorithm
- Look for the existence of a target string in another string
- Return the index of the first occurrence of target
- Raise exception if target is not found
Pseudocode
- Set n = length of string
- Set m = length of target
- For i = 0 to n - m
- Set j = 0
- While j < m and target[i] equals string[i + j]
- increment j
- end while
- if j equals m then return i
- raise exception
Complexity
n is the length of the string and m is the length of the target
| cases | complexity | description |
|---|---|---|
| best case | O(m) | target is at the beginning |
| average case | O(mn) | target is in the middle |
| worst case | O(mn) | target is not found |