Problem of the day
You are given an integer array 'A' of size 'N', sorted in non-decreasing order. You are also given an integer 'target'. Your task is to write a function to search for 'target' in the array 'A'. If it exists, return its index in 0-based indexing. If 'target' is not present in the array 'A', return -1.
You must write an algorithm whose time complexity is O(LogN)
The first line contains an Integer 'N', which denotes the size of the array/list.
The second line contains 'N' single space-separated integers representing the elements in the array/list.
The third line contains the value of 'target' to be searched for in the array/list.
Output Format :
Return the index at which 'target' is present for each test case, -1 otherwise.
1 <= N <= 10^5
1 <= A[i] <= 10^9
1 <= target <= 10^9
Time Limit: 1 sec
7
1 3 7 9 11 12 45
3
1
nums = [1, 3, 7, 9, 11, 12, 45],
The index of element '3' is 1.
Hence, the answer is '1'.
7
1 2 3 4 5 6 7
9
-1
nums = [1, 2, 3, 4, 5, 6, 7],
Element '9' doesn't exist.
Hence, the answer is '-1'.
Apply Binary Search.
Since our array is sorted, we can apply binary search here. We will keep two variables, ‘s’ and ‘e’, initially assigned to ‘0’ and ‘length of the array’, respectively. At each iteration, we will first calculate the middle value of ‘s’ and ‘e’ and store it in a variable called ‘mid’. Then we will check the following conditions:
If we don’t find any index, we will return ‘-1’.
The steps are as follows:-
// Function to find the element ‘target’
function search(int[] nums, int n, int target):
O( N * logN ), where 'N' is the size of the array ‘nums’.
We are using the binary search here,
Hence the time complexity is O( N * logN ).
O( 1 ).
We are only using some variables,
Hence the space complexity is O( 1 ).