/**
 * @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
}