Concept

Concept#

Twitter Handle LinkedIn Profile

Introduction#

Linear search, also known as sequential search, is a fundamental algorithm in the field of computer science, serving as a bedrock for understanding more complex algorithms. It represents the most intuitive method of searching for an element within a list. The simplicity of linear search lies in its straightforward approach: examining each element in the list sequentially until the desired element is found or the end of the list is reached.

This algorithm, in its essence, begins with the assumption of an unordered list. Without any prior knowledge of the arrangement of elements, linear search treats each item in the list with equal importance, methodically checking each until a match is found. This aspect of linear search, while simple, is crucial in understanding how more complex searching algorithms evolve and optimize under different conditions.

Extensions#

As we progress from the basic unordered scenario, the concept of an ordered list introduces a subtle yet significant shift in the algorithm’s operation. In an ordered list, the elements are arranged in a known sequence, either ascending or descending. This arrangement allows for certain optimizations in the search process. For instance, the search can be terminated early if the current element in the sequence is greater (or lesser, depending on the order) than the element being searched for, as it confirms the absence of the target element in the remaining part of the list.

Furthermore, exploring the concept of a probabilistic array adds another dimension to our understanding of linear search. In a probabilistic setting, each element’s likelihood of being the target is different and known. This knowledge can be leveraged to modify the traditional linear search into a more efficient version, where the order of search is determined based on the probability of finding the target element, thus potentially reducing the average number of comparisons needed.

Intuition#

The linear search algorithm operates on a fundamental principle of sequential access in data structures. This intuition is best understood by considering the data structure it commonly operates on, such as a list. In computer science, the representation of a list in memory is typically implemented as a linear data structure. This means that the elements of the list are stored in contiguous memory locations. Each element in the list is stored at a memory address that sequentially follows the previous element, adhering to a defined order. Although not strictly relevant to the algorithm, having spatial locality between elements in the list enables efficient access and traversal operations.

To elucidate the mechanism of linear search, let’s consider the task of locating a specific target element \(\tau\) within a list \(\mathcal{A}\). The process unfolds in a sequential manner: beginning with the first element, the algorithm examines each subsequent element in turn. This sequential traversal is the hallmark of linear search, distinguishing it from more complex search algorithms that may jump or divide the list in their search process.

../../../_images/linear-search-1.svg

Fig. 62 Linear Search Algorithm.#

Tikz Code

\documentclass[tikz,border=10pt]{standalone}
\usepackage{tikz}
\usetikzlibrary{arrows.meta, positioning}

\begin{document}
\begin{tikzpicture}[
    box/.style={draw, rectangle, minimum size=1cm, thick, outer sep=0pt},
    index/.style={above, font=\footnotesize},
    arrow/.style={thick, -Stealth, bend left=60}
]

% Draw boxes and indices
\foreach \x [count=\i] in {10,50,30,70,80,60,20,90,40} {
    \node[box] (box\i) at (\i-1,0) {\x};
    \node[index] at (box\i.north) {\number\numexpr\i-1\relax}; % Place index
}

% Draw arrows
\foreach \i [evaluate=\i as \nexti using int(\i+1)] in {1,...,6} {
    \draw[arrow] ([yshift=5mm]box\i.north) to ([yshift=5mm]box\nexti.north);
}

% Draw the "Find '20'" label
\node[above=of box1, align=center, yshift=15mm] (find) {Find '20'};

% Connect the "Find '20'" label with the starting arrow
\draw[arrow] (find.south) to ([yshift=5mm]box1.north);

% Highlight the found box
\node[box, fill=green!30] at (box7) {20};

\end{tikzpicture}
\end{document}

As the algorithm progresses through list \(\mathcal{A}\), searching for the target element \(\tau\), there are two primary outcomes to consider:

  1. Element Discovery: If the element \(\tau\) is encountered at any point during the traversal, the search is immediately successful. The algorithm can then return a positive result, such as True, or, more informatively, the index \(i\) at which \(\tau\) was found in \(\mathcal{A}\). Returning the index \(i\) provides not only confirmation of the element’s presence but also its exact location within the list. This outcome signifies that \(\tau = \mathcal{A}[i]\), where \(\mathcal{A}[i]\) denotes the element at the \(i^{th}\) position in list \(\mathcal{A}\).

  2. Exhaustive Search without Discovery: Conversely, if the traversal reaches the end of the list without encountering \(\tau\), it implies that the element is not present in \(\mathcal{A}\). In this case, the algorithm concludes with a negative result, typically returning False. This denotes that for all indices \(i\) in \(\mathcal{A}\), \(\tau \neq \mathcal{A}[i]\).

The simplicity of this approach is its most defining characteristic (read: brute force). Unlike algorithms that rely on specific data structure properties (such as binary search, which requires a sorted array), linear search makes no such assumptions. It treats each element in \(\mathcal{A}\) with equal priority and does not benefit from any particular arrangement of the data. We will see later on some extensions of linear search that leverage the ordering of elements to optimize the search process or if the list is probabilistic.

Summary#

In conclusion, while linear search is one of the simplest search algorithms, its variations like ordered and probabilistic searches demonstrate its adaptability and effectiveness in diverse scenarios. From basic implementations in unordered lists to more sophisticated applications in sorted and probabilistic lists, linear search remains a crucial tool in the algorithmic toolkit. It is also a good “naive/brute-force” approach to solving problems.

References and Further Readings#