Solution Review: Find Closest Number

Solution # 1

A simple and straightforward solution to this problem is to traverse through the array while computing and keeping track of the minimum absolute difference of each array element with the target number. Finally, you’ll 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 an $O(n)$ solution.

Instead of using this method, we can exploit the fact that the array is sorted and apply 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; we can drop one half of the array at each step, knowing that the other half must have elements with a lesser absolute difference.