Linear Search
Linear Search
Linear search is the simplest search algorithm. It scans elements of a sequence sequentially, one by one, checking whether the target element matches the current element. This is useful for unsorted arrays or when data is simple and unsorted, though highly inefficient for larger arrays.
Complexity Profile
| Case | Complexity |
|---|---|
| Best Case | O(1) |
| Average Case | O(N) |
| Worst Case | O(N) |
| Space Complexity | O(1) |
Code Implementation
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i # Target index found
return -1 # Target not foundReal-World Applications
- Searching in unsorted collections.
- Small datasets where overhead of sorting exceeds search time.
- Input validation and checking presence in basic arrays.
DFS
Depth-First Search (DFS) is a graph traversal algorithm that explores as deep as possible along each branch before backtracking. It relies on a LIFO Stack (or call stack recursion) to navigate vertices. DFS is essential for topological sorting, detecting cycles, and solving maze puzzles.
Merge Sort
Merge Sort is a stable, divide-and-conquer sorting algorithm. It recursively splits the input array into two halves, sorts each half individually, and merges the sorted sub-arrays. It ensures consistent O(N log N) speeds, though it requires auxiliary memory to merge elements.