The Sentinel Search: Optimize Linear Search with a Sentinel

In the border patrol of Prime City, the Captain uses a clever trick to speed up linear search. By placing a "sentinel" ÔÇö the target value itself ÔÇö at the end of the array, the patrol can eliminate the bounds check in each iteration. The search always finds the sentinel, so the loop never needs to check if the index is within bounds. "Place the target at the end of the array," the Captain says. "Then scan from the beginning without any bounds checking. When you find the target, check if the index is within the original array bounds. If it is, you found the real target. If not, the target wasn't in the array." Given an array of N integers and a target T, use sentinel search to find the index of T. If T is not in the array, output -1. Output the 0-based index. Constraints: 1 <= N <= 10^5, -10^9 <= array[i], T <= 10^9 Input: 5 3 1 4 1 5 4 Output: 2 Input: 3 1 2 3 5 Output: -1