Explain what is Linear (Sequential) Search and when may we use one?

Linear search, also known as sequential search, is a fundamental search algorithm used to locate a specific element within a list or array. It operates by examining each element in the list one by one, in sequence, from the beginning to the end, until the desired element is found or the list is completely searched[1][2][3][4][5][6][7][8][9][10][11].

The process of linear search is straightforward:

1. Start at the beginning of the list.
2. Compare each element with the target value.
3. If a match is found, return the index of the element.
4. If no match is found by the end of the list, return an indication that the element is not present (such as -1 or NULL).

Linear search is characterized by its simplicity and lack of prerequisites for the data structure's organization. It does not require the list to be sorted and can be applied to any collection of elements, whether it's an array, linked list, or another linear data structure[1][2][3][4][5][6][7][8][9][10][11].

The time complexity of linear search is O(n), where n is the number of elements in the list. This means that in the worst case, the algorithm may have to inspect each element once, making it less efficient for large datasets. The space complexity is O(1), as it requires a constant amount of additional memory regardless of the size of the input list[2][3][4][5][7][8][9].

Linear search may be used in the following scenarios:

• When the list is small: Due to its simplicity, linear search can be efficient for small lists where the overhead of more complex algorithms is not justified[3][4][5][7][8][9].
• When the list is unsorted: If the list is not sorted and cannot be sorted due to constraints, l...