S

```
/**
* @function sentinelSearch
* @description Sentinel search algorithm for array.
*
* Sentinel linear search is a variation of the standard linear search algorithm used to
* find a target value in an array or list. The basic idea behind this algorithm is to add a
* sentinel value at the end of the array which is equal to the target value we are looking for.
* This helps to avoid checking the array boundary condition during each iteration of the loop,
* as the sentinel value acts as a stopper for the loop.
*
* @param {number[]} array - sorted list of numbers
* @param {number} target - target number to search for
* @return {number|null} - index of the target number in the list, or null if not found
* @see [SentinelSearch](https://www.geeksforgeeks.org/sentinel-linear-search/)
* @example sentinelSearch([1,2,3], 2) => 1
* @example sentinelSearch([4,5,6], 2) => null
* @complexity_analysis
* Time Complexity :
* Worst Case -> The time complexity of the Sentinel Linear Search algorithm is O(n) in the worst case.
* Best Case -> In the best case, when the key is found in the first iteration, the time complexity will be O(1).
* Average Case -> However, the average time complexity is still O(n).
* Auxiliary Space: O(1)
*/
export const sentinelSearch = (
array: number[],
target: number
): number | null => {
const arrayLength = array.length
if (arrayLength === 0) return null
// Element to be searched is placed at the last index
const last = array[arrayLength - 1]
array[arrayLength - 1] = target
let index: number = 0
while (array[index] !== target) index += 1
// Put the last element back
array[arrayLength - 1] = last
if (index < arrayLength - 1 || array[arrayLength - 1] === target) return index
return null
}
```