Solution: Find the Closest Number

This review discusses the solution of finding the closest number challenge in detail.

Solution#1

A simple solution to this problem can be to traverse through the array while computing the minimum absolute difference of each array element with the target. Finally, return the element that has the minimum absolute difference.

Time complexity

Since we have to go through each element one by one and compute its absolute difference, this solution is implemented in O(n)O(n) time.

Instead of using this method, we can make use of the fact that the array is sorted, and we can devise a more efficient solution to find the closest number.

Solution#2: efficient

Since we know that the array is sorted, an efficient solution to solve this problem would work like a binary search algorithm, where at each step we can drop one half of the array, knowing that the other half must have elements with a lesser absolute difference.

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.