A value in an algorithm that symbolizes a special state.
In C++, do your best to avoid using sentinel values when possible
>[!example]
> Some implementations of linear search in C return a sentinel value of $-1$ to signify failure.
>
>```c
>
>int find(int* arr, size_t length, int target) {
> for (size_t i = 0; i < length; i++) {
> if (arr[i] == target) return i;
> }
> return -1; // could not find
>}
>```
> While using a sentinel value is what we are limited to in C, in C++ / [[Rust]] you could use encode the possibility of failure into the [[Type System]].
>
>*C++*:
>```cpp
>std::optional<std::size_t> find(
> int* array,
> std::size_t length,
> int target
>) {
>
> for (size_t i = 0; i < length; i++) {
> if (array[i] == target) return std::make_optional(i);
> }
>
> return std::nullopt;
>}
>```
>
>*Rust*:
>```rust
>fn find(array: &[i32], target: i32) -> Option<usize> {
> for (element, i) in array.iter().enumerate() {
> if *element == target { return Some(i); }
> }
> return None;
>}
>```