Given a sorted integer array arr[] of n elements and a target value k, write a program to search k in arr[].

Problem Note

• If k exists, then return its index, otherwise, return -1.
• You may assume that all elements in arr[] are unique.

Example 1

Input: arr[] = [1, 5, 6, 7, 9, 10, 50], k= 9
Output: 4
Explanation: 9 exists in arr[] and its index is 4.

Example 2

Input: arr[] = [1, 5, 6, 7, 9, 10, 50], target = 20
Output: -1
Explanation: 20 does not exist in arr[] so return -1.