What is Linear Search?

Linear search, also known as sequential search, is the simplest searching algorithm. It works by sequentially checking each element of a list or array until a match is found or the entire list has been searched. It's straightforward to understand and implement, making it a good starting point for learning about searching algorithms. However, it's not very efficient for large datasets.

Detailed Explanation of the Linear Search Algorithm

Implementation

The basic idea behind linear search is to iterate through each element of the array/list and compare it with the element you're searching for (the 'key'). If a match is found, the algorithm returns the index of the element. If the key isn't found after checking all elements, the algorithm typically returns -1 (or a similar indicator that the element is not present).

Algorithm Steps:

1. Start at the first element of the array (index 0).
2. Compare the current element with the search key.
3. If the current element matches the key, return the index of the current element.
4. If the current element does not match the key, move to the next element in the array.
5. Repeat steps 2-4 until either a match is found or the end of the array is reached.
6. If the end of the array is reached without finding a match, return -1.

Example (Python):

  def linear_search(arr, key):
    """
    Performs a linear search on the given array for the specified key.

    Args:
        arr: The array to search.
        key: The element to search for.

    Returns:
        The index of the key in the array if found, otherwise -1.
    """
    for i in range(len(arr)):
        if arr[i] == key:
            return i  # Key found at index i
    return -1  # Key not found

# Example usage:
my_array = [10, 5, 8, 2, 9, 1, 7]
search_key = 9
index = linear_search(my_array, search_key)

if index != -1:
    print(f"Key {search_key} found at index {index}")
else:
    print(f"Key {search_key} not found in the array") 

Example (JavaScript):

  function linearSearch(arr, key) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === key) {
            return i; // Key found at index i
        }
    }
    return -1; // Key not found
}

// Example Usage
const myArray = [10, 5, 8, 2, 9, 1, 7];
const searchKey = 9;
const index = linearSearch(myArray, searchKey);

if (index !== -1) {
    console.log(`Key ${searchKey} found at index ${index}`);
} else {
    console.log(`Key ${searchKey} not found in the array`);
} 

Time Complexity Analysis

Time complexity describes how the runtime of an algorithm grows as the input size increases. We analyze it in three scenarios: best-case, worst-case, and average-case.

Best-Case Time Complexity: O(1)

The best case occurs when the key is found at the very first position in the array. In this scenario, only one comparison is needed. The algorithm immediately finds the key and returns. Therefore, the time complexity is constant, denoted as O(1).

Worst-Case Time Complexity: O(n)

The worst case happens when the key is either not present in the array or is located at the last position. In this case, the algorithm needs to iterate through all n elements of the array to either find the key at the last element or determine that it's not present. Therefore, the time complexity is linear, denoted as O(n), where n is the number of elements in the array.

Average-Case Time Complexity: O(n)

The average case considers the expected number of comparisons when the key is equally likely to be found at any position in the array or not found at all. On average, the algorithm will need to examine approximately n/2 elements. Since constant factors are ignored in Big O notation, the average-case time complexity is also O(n).

Space Complexity: O(1)

Linear Search has a constant space complexity. It only requires a fixed amount of extra memory, regardless of the size of the input array. Typically, this involves storing the index counter 'i' and perhaps the key being searched for. Therefore, the space complexity is O(1).