Searching Algorithms Analysis

Linear Search

Linear Search is the simplest searching algorithm. It works by sequentially checking each element of the array or list until it finds the target element. If the target is found, the algorithm returns its position; otherwise, it continues until the end of the data structure and returns a negative result (indicating that the element is not present).

Algorithm Steps:

1. Start from the first element of the array.
2. Compare the current element with the target element.
3. If they match, return the index of the current element.
4. If they don't match, move to the next element.
5. Repeat the process until the target element is found or the array ends.

1def linear_search(arr, target):
2    for index, element in enumerate(arr):
3        if element == target:
4            return index  # Target found, return its index
5    return -1  # Target not found
6
7# Example usage
8arr = [5, 3, 8, 4, 2]
9target = 8
10result = linear_search(arr, target)
11print(f"Element {target} found at index: {result}")  # Output: Element 8 found at index: 2
12

Complexity Analysis:

• Time Complexity: O(n)
• Space Complexity: O(1)

Binary Search

Binary Search is a much more efficient algorithm compared to Linear Search, but it requires the array to be sorted. It works by repeatedly dividing the search interval in half. If the target value is less than the middle element, the search continues in the left half; if it's greater, it continues in the right half. This process continues until the target is found or the interval is empty.

The binary search algorithm may seem easy at first, and it is, but its extended versions can become complex and lead to more powerful algorithms. Some of these extended versions include Ternary Search, a variation of binary search that divides the array into three parts instead of two. Some of the LeetCode problems that help in understanding the algorithm are:

• 704. Binary Search
• 74. Search a 2D Matrix
• 33. Search in Rotated Sorted Array
• 4. Median of Two Sorted Arrays

Algorithm Steps:

1. Start with the entire array.
2. Find the middle element of the array.
3. Compare the middle element with the target:
• If the middle element is equal to the target, return the index of the middle element.
• If the middle element is less than the target, search the right half of the array.
• If the middle element is greater than the target, search the left half of the array.
4. Repeat the process on the selected half until the target is found or the array is exhausted.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3
4    while left <= right:
5        mid = (left + right) // 2
6
7        if arr[mid] == target:
8            return mid  # Target found, return its index
9        elif arr[mid] < target:
10            left = mid + 1  # Continue search in the right half
11        else:
12            right = mid - 1  # Continue search in the left half
13
14    return -1  # Target not found
15
16# Example usage
17arr = [2, 3, 4, 5, 8]
18target = 8
19result = binary_search(arr, target)
20print(f"Element {target} found at index: {result}")  # Output: Element 8 found at index: 4
21

Complexity Analysis:

• Time Complexity: O(log n)
• Space Complexity: O(1)

Searching Algorithms Analysis

Understanding the nuances of Linear and Binary Search is essential for anyone delving into the world of algorithms. While Linear Search offers simplicity, Binary Search provides efficiency—particularly with large, sorted datasets. Knowing when to use each algorithm and analyzing their time and space complexities can significantly impact the performance of your applications.

References

• https://www.geeksforgeeks.org/searching-algorithms/