...

/

Solution: Find the Closest Number

Solution: Find the Closest Number

Review various solution approaches to find the closest number to a given number in an array in detail.

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 difference
int index = 0; // Array index number
for (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 number
index = i; // Saving the index of the array
}
}
return arr[index]; // Returning the result
}
// Driver code to test above method
public 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 the target.
  • 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 O(n ...