Sequential Search

Problem Solved

Design and Strategy

Sequential Search (also called Linear Search) is a classic brute-force algorithm: it makes no assumptions about the order of the data and exhaustively tests every element. Starting at index 0, it compares the value of each element to the target value; if a match is found, it immediately returns the index of that element. Otherwise, it moves to the next element, continuing until either the target is located or the end of the array is reached at which point it returns -1. Because it “tries every possibility,” you are guaranteed to find the target if it is present with no more than n comparisons.

More formally, the algorithm works as follows:

1. Start with index i = 0.
2. Compare A[i] with target.
3. If they are equal, return i.
4. Otherwise, increment i.
5. If i==n (end of the array), return -1. Otherwise, repeat from step 2.

Implementation in Java, C++, Python

public int sequentialSearch(int[] A, int target) {
  for (int i = 0; i < A.length; i++) {
    if (A[i] == target) {
      return i;
    }
  }
  return -1;
}

int sequentialSearch(int A[], int n, int target) {
  for (int i = 0; i < n; i++) {
    if (A[i] == target) {
      return i;
    }
  }
  return -1;
}

def sequential_search(A, target):
  for i, value in enumerate(A):
    if value == target:
      return i
  return -1

Time/Space Analysis

Time Complexity: We count the number of element-to-target comparisons as our cost metric. If the target is found at position k, then k comparisons were executed since it compare the target with each of the first k elements until it found it. If the target is not present, then it compared the target with every element of the array, so it did m comparisons.

From this we can see:

• Best-case: O(1) comparisons (e.g. target is at the first position).
• Worst-case: O(n) comparisons (e.g. target is at the last position or absent).
• Average-case: Assuming the searched value is equally likely to be present or absent:
  • Value present: On average, the algorithm finds the value after checking about n/2 elements.
  • Value absent: The algorithm always checks all n elements.
  Thus, in either case, the average complexity is O(n).

Space Complexity: The iterative sequential search uses only a fixed number of additional variables: The loop index i, the space for the target, and the return value. and a few constant‐size temporaries (if any). Thus, the space complexity is O(1).

Links to Resources

• Search Demo (linear vs binary)

Reading Comprehension Questions

1. Q1: What is the best-case time complexity for Sequential Search, and when does it occur?
2. Q2: What is the worst-case time complexity for Sequential Search, and when does it occur?
3. Q3: What algorithm technique does Sequential Search use, how do you know?
4. Q4: If the array contains multiple copies of the target, which index will this implementation return?
5. Q5: What is the space complexity of this algorithm?
6. Q6: How would you modify the algorithm to return all indices where the target occurs?

In-Class Activities

1. Walk through the algorithm on different arrays to count comparisons.
2. Discuss how the target’s position affects performance.
3. Compare and contrast with Binary Search on sorted data. Discuss in which cases you would use each.
4. Explore handling of duplicate targets in various implementations.
5. Simulate a sentinel-based Sequential Search: place a copy of the target at the end to eliminate the boundary check, then compare the number of comparisons and loop logic to the standard version.

Problems

1. Write code or pseudocode for a recursive version of Sequential Search.
2. Adapt sequential search to operate on a singly linked list (with pseudocode).
3. Write code or pseudocode for the version of the algorithm to return all indices where the target occurs (not just the first). Analyze how this changes your time and space complexity.
4. Implement a sentinel-based sequential search: before scanning, append the target as a sentinel at the end of the array to remove the explicit bounds check; then compare its performance (number of comparisons and code branches) against the standard implementation. Discuss any drawbacks of this approach.