]], also known as , is a basic searching used to find a particular value in an or . It involves examining each in the list sequentially until a match is found or all elements have been searched.
The search process begins at the first of the list and continues until the target element is found or the end of the list is reached. To perform the search, a between the target element and each element in the list is made. If a match is found, a value indicating the presence or absence of the target element is returned.
One of the key factors in evaluating the of an algorithm is its , which refers to how the algorithm's execution time increases with the size of the input. In the case of Sequential Search, the runtime complexity is linear, commonly denoted as , where n represents the number of elements in the list.
In the , the target element is located at the end of the list or is absent from the list entirely. In such cases, the algorithm's performance is at its poorest, as it has to traverse through all the elements until reaching the end or determining the absence of the target element. Consequently, the worst-case scenario has a of O(n).
Conversely, in the , the target element is found at the first index, resulting in the algorithm's fastest execution. However, even in this case, the algorithm still has to traverse through the list once to confirm the presence of the target element. The best-case scenario still exhibits a linear time complexity of O(n).
The takes into consideration various input distributions. On average, the algorithm would need to search through half of the list, resulting in a linear time complexity of O(n/2). However, in the analysis of algorithms, the average-case scenario is generally simplified to the worst-case scenario. This simplification is done as it provides a conservative estimate of the algorithm's efficiency.
Keywords
comparison | runtime | worst-case scenario | complexity | unordered | list | average-case scenario | o(n) | index | efficiency | array | algorithm | best-case scenario | linear time complexity | element | linear search | sequential [[search | boolean |
