The Bidirectional Search: Search from Both Ends

In the search parties of Prime City, the Captain deploys two scouts ÔÇö one from each end of the array. They walk toward each other, checking each element. This bidirectional approach can find the target in roughly half the time of a standard linear search. "Send one scout from the left and one from the right," the Captain says. "They check elements simultaneously. If either finds the target, return that index. If they meet in the middle without finding it, the target isn't in the array." Given an array of N integers and a target T, use bidirectional search to find the index of T. If T appears multiple times, return the first index found by either scout (left scout has priority). If T is not found, output -1. Constraints: 1 <= N <= 10^5, -10^9 <= array[i], T <= 10^9 Input: 5 3 1 4 1 5 4 Output: 2 Input: 6 1 2 3 4 5 6 6 Output: 5