---
title: "Sequential search and sentinel"
subject: "Data Structure and Algorithm"
chapter: 8
key: "semester_4/data_structure_and_algorithm:sequential-search-sentinel"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/sequential-search-sentinel
site: BCT Engineering
---

# Sequential search and sentinel

Data Structure and Algorithm · Chapter 8: Searching

- Asked in: 2068 Magh, 3 marks
- Video: [Sentinel search algorithm | Searching algorithm | Sequential searching](https://www.youtube.com/watch?v=PPDBcQOPZbc) — For CS
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/sequential-search-sentinel
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-8

## Question

What is sequential search and how is sentinel useful in this algorithm?

## Short answer

Sequential search checks elements one by one until key is found. A sentinel (key stored at a[n]) eliminates the end-of-array test, so only a[i]!=key is tested per iteration, speeding up the search.

## Answer

**Sequential (linear) search** examines the elements of a list one by one from the first element until the key is found or the end of the list is reached. It works on unsorted data. The best case is 1 comparison, the worst and average cases are n and about (n+1)/2 comparisons, so it is O(n).

```c
int seqSearch(int a[], int n, int key) {
    for (int i = 0; i < n; i++)      /* two tests per iteration */
        if (a[i] == key) return i;
    return -1;
}
```

#### Use of sentinel
A **sentinel** is the key itself stored in one extra location at the end (a[n] = key). The search is then guaranteed to succeed, so the end-of-array test is not needed in each iteration, and only one comparison is made per step.

```c
int seqSearchSentinel(int a[], int n, int key) {
    int i = 0;
    a[n] = key;                  /* sentinel stored after last element */
    while (a[i] != key) i++;     /* only one comparison per step */
    return (i < n) ? i : -1;     /* i == n means not found */
}
```

For list 7, 3, 9 (n = 3) and key 5: a[3] = 5, i moves 0, 1, 2, 3 and stops at 3. Since i == n, the result is "not found".

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. Which is true of sequential search?
   A. Needs sorted data
   B. Examines elements one by one, O(n)
   C. O(log n)
   D. Needs a hash
   Answer: B. It works on unsorted data. (Key point: Sequential search)

2. Where is the sentinel stored?
   A. In a[0]
   B. In a[n], one extra location after the last element
   C. In a[n-1]
   D. In a separate flag only
   Answer: B. The array needs a spare slot. (Key point: Sentinel)

3. For list 7, 3, 9 and key 5, how does the sentinel version end?
   A. i stops at 3 = n, not found
   B. i stops at 0
   C. Infinite loop
   D. Returns 2
   Answer: A. i == n means not found. (Key point: Not found)

## Related in Data Structure and Algorithm

- [Sentinel in sequential search](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Asentinel-sequential-search-importance) — Data Structure and Algorithm, chapter 8
- [Sequential vs binary search](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Asequential-vs-binary-search) — Data Structure and Algorithm, chapter 8
- [Binary search with algorithm and example](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abinary-search-algorithm-example) — Data Structure and Algorithm, chapter 8, asked 4×