Encontre o Índice (Parte #2)

Crie uma função que pesquise o índice de um elemento fornecido em um array usando recursão. Se o elemento estiver presente, ela deverá retornar o índice; caso contrário, deverá retornar -1.

Exemplos

Search({1, 2, 3, 4}, 3) ➞ 2

Search({2, 4, 6, 8, 10}, 8) ➞ 3

Search({1, 3, 5, 7, 9}, 11) ➞ -1

Observações

• Use recursão.
• Evite usar Linq.
• Se o elemento não estiver presente, retorne -1.
• O array fornecido está ordenado.