/* sentinel.c Example search program using sentinels */ /* Copyright 2003-2020 by Steven S. Skiena; all rights reserved. Permission is granted for use in non-commerical applications provided this copyright notice remains intact and unchanged. These programs appear in my books: "The Algorithm Design Manual" by Steven Skiena, second edition, Springer, London 2008. See out website www.algorist.com for additional information or https://www.amazon.com/exec/obidos/ASIN/1848000693/thealgorith01-20 "Programming Challenges: The Programming Contest Training Manual" by Steven Skiena and Miguel Revilla, Springer-Verlag, New York 2003. See our website www.programming-challenges.com for additional information, or https://www.amazon.com/exec/obidos/ASIN/0387001638/thealgorithmrepo/ */ #include #define MAXINT 1000000 int a[100]; int main(void) { int i, n, x; for (i = 1; i <= 20; i++) { a[i] = i; } n = 20; x = -1; i = n; while ((a[i] >= x) && (i >= 1)) { a[i + 1] = a[i]; i = i - 1; } a[i + 1] = x; printf("without sentinel, i=%d a[1]=%d\n", i, a[1]); for (i = 1; i <= 25; i++) { printf("%d ", a[i]); } x = -2; n = 21; i = n; a[0] = - MAXINT; while (a[i] >= x) { a[i + 1] = a[i]; i = i - 1; } a[i + 1] = x; printf("\nwith sentinel, i=%d a[1]=%d\n", i, a[1]); for (i = 1; i <= 25; i++) { printf("%d ", a[i]); } return 0; }