/**
 * @file
 * @brief [Linear Search with Sentinel](https://en.wikipedia.org/wiki/Linear_search#With_a_sentinel) algorithm implementation
 * @details
 * This algorithm saves the last element of the array, 
 * then replaces it with the value to be found and sets it as the sentinel. 
 * When searching, compares each element with the sentinel. 
 * If the same, returns the index. If the index is the index of the sentinel, it means it was not found. 
 * Of course, if the value to be found is the last element, we return the index of the last element.
 * @author [Regan Yue](https://github.com/ReganYue)
 * Time Complexity: O(N)
 */

#include <stdio.h>   /// for IO operations
#include <assert.h>  /// for assert

/**
 * @brief Utility function to search for an element in the array and return the index of the element
 * @details 
 * The so-called "sentinel" is to use a special value as the boundary key of the array. 
 * One less judgment statement can be used. 
 * The purpose is to avoid checking whether the entire array is searched at each step in the search 
 * process, so as to improve the efficiency of the program.
 * We can use the last value of the array as the "sentinel", the data storage index i 
 * starts from 0 and ends at len-1, then the position where the index of arr is n-1 indicates 
 * that there is no data temporarily, which is the "sentinel" key.
 * If the last element of the array is equal to the key, directly return the index of the last element. 
 * Before setting the last element of the array as the key, we hand over the last element of the array to temp for temporary storage. 
 * Then go to the array to find the key. If the key is found, stop the search, and then compare the found element index with len-1. 
 * If it is equal, it means it was not found. If it is not equal, it is found.
 * @param arr this is an array containing elements
 * @param len this is the number of elements in the array
 * @param key the value we want to search
 * @return i if found, otherwise -1 is returned.
 */
int sentinel_linear_search( int arr[], int len, int key ){
	if(key == arr[len-1]){
		return len-1;
	}
	
	int temp = arr[len-1]; 
	arr[len-1] = key;
	
	int i = 0;
	while (arr[len-1] != arr[i]) {
		i++;
	}
	
	arr[len-1] = temp;
	
	return i != len-1 ? i : -1;
	 
}

/**
 * @brief Self-test implementations
 * @returns void
 */
static void test(){
	int n,i;
	n = 5;
	/* init array */
	int arr[] = { 1, 2, 2, 6, 99, 100, 999 };

	assert(sentinel_linear_search( arr, n, 1 )==0);
	assert(sentinel_linear_search( arr, n, 2 )==1);
	assert(sentinel_linear_search( arr, n, 6 )==3);
	assert(sentinel_linear_search( arr, n, 101 )==-1);
	printf("All test cases have successfully passed!\n");
} 

/**
 * @brief Main function
 * @returns 0 on exit
 */
int main(){
	test();  // run self-test implementations
	return 0;
}