Given an array A = [10, 7, 4, 2, 1], and target = 7, return the index of the target if found, else return -1. 1. Can this problem be solved in O(logN)? 2. If so, write the implementation. Mention time and space complexity 3. If this problem cannot be solved using O(logN), what is the solution that you suggest - write the code and also mention time and space complexity.
Given an array A = [10, 7, 4, 2, 1], and target = 7, return the index of the target if found, else return -1.
1. Can this problem be solved in O(logN)?
2. If so, write the implementation. Mention time and space complexity
3. If this problem cannot be solved using O(logN), what is the solution that you suggest - write the code and also mention time and space complexity.
Yes, this problem can be solved in O(logN) time complexity using a binary search since the input array is sorted.
Binary search works on the divide and conquer principle.
In this algorithm the list is divided into two halves, and the search element is compared with the middle element of the list.
If the match is found then, the index of the middle element is returned.
Otherwise,
If the search element is greater than the middle element, we search in the upper sub-array.
If the search element is less than the middle element, we search in the lower sub-array.
Step by step
Solved in 3 steps
