Sequential search and sentinel

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).

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.

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".