Solution: Find the Closest Number
Review various solution approaches to find the closest number to a given number in an array in detail.
We'll cover the following...
Solution 1
A simple and straightforward solution to this problem would be to compute the absolute difference of the target from each array element iteratively while keeping track of the minimum difference encountered so far.
using System;public class Program{/// <summary>/// Finds the closest number to the target in the array./// </summary>/// <param name="arr">Sorted array of integers.</param>/// <param name="target">Target integer.</param>/// <returns>The closest element from the array to the target.</returns>public static int FindClosest(int[] arr, int target){int closest = Math.Abs(arr[0] - target); // Closest absolute differenceint index = 0; // Array index numberfor (int i = 0; i < arr.Length; i++) // Traversing the whole array{if (Math.Abs(arr[i] - target) <= closest) // Is there any number more closest?{closest = Math.Abs(arr[i] - target); // Saving the new closest numberindex = i; // Saving the index of the array}}return arr[index]; // Returning the result}// Driver code to test above methodpublic static void Main(string[] args){Console.WriteLine(FindClosest(new int[] { -9, -4, -2, 0, 1, 3, 4, 10 }, 5));Console.WriteLine(FindClosest(new int[] { 1, 2, 5, 10, 23, 25, 30, 50 }, 100));}}
Explanation
- Lines 13–14: We initially save the first index of the array and its index as the
closest
number. - Lines 18–22: While traversing the whole array, we store the
closest
number and its index to thetarget
. - Lines 25: We return the
closest
element from the array.
Time complexity
Since we have to go through each element one by one and compute its absolute difference, this solution is an ...