You are given a sorted and infinite array arr[] and an element key . Write a program to search for the element key in the array. If found, return the index of the element, else return -1.

Problem Note

• Infinite array means we don't know the upper bound of the array.

Example 1

Input: 
arr[] = [1, 3, 5, 8, 12, 13, 17, 19, 28, 39,...], key = 17
Output: 6
Explanation: The key 17 is found at the index 6.

Example 2

Input: 
arr[] = [10, 20, 25, 30, 67, 93, 159, 192,.....], key = 23
Output: -1
Explanation: The key 23 is not present in the given array, so return -1.