<?php
/* SentinelSearch
Input : -
parameter 1: Array
parameter 2: Target element
Output : -
Returns index of element if found, else -1
*/
function SentinelSearch($list, $target)
{
//Length of array
$len = sizeof($list);
//Store last element of array
$lastElement = $list[$len - 1];
//Put target at the last position of array known as 'Sentinel'
if ($lastElement == $target) {
return ($len - 1);
}
//Put target at last index of array
$list[$len - 1] = $target;
//Initialize variable to traverse through array
$i = 0;
//Traverse through array to search target
while ($list[$i] != $target) {
$i++;
}
//Put last element at it's position
$list[$len - 1] = $lastElement;
//If i in less than length, It means element is present in array
if ($i < ($len - 1)) {
return $i;
} else {
return -1;
}
}