0% completed

Solution: Minimum Difference Element

Problem Statement

Given an array of numbers sorted in ascending order, find the element in the array that has the minimum difference with the given ‘key’.

Example 1:

Input: [4, 6, 10], key = 7
Output: 6
Explanation: The difference between the key '7' and '6' is minimum than any other number in the array

Example 2:

Input: [4, 6, 10], key = 4
Output: 4

Example 3:

Input: [1, 3, 8, 10, 15], key = 12
Output: 10

Example 4:

Input: [4, 6, 10], key = 17
Output: 10

Solution

The problem follows the Binary Search pattern

.....

Like the course? Get enrolled and start learning!

L

Learner

· 5 years ago

Show 2 replies

L

lejafilip

· 2 years ago

  static int searchMinDiffElement(const vector<int>& arr, int key) {
    if(arr[arr.size() - 1] <= key)
      return arr[arr.size() - 1];
    else if(arr[0] >= key)
      return arr[0];

    std::pair<int, int> minDiff{std::numeric_limits<int>::max(), -1};
    auto start = 0;
    auto end = arr.size() - 1;
    
    while(start <= end)
    {
      auto mid = (start + end) / 2;

      if(arr[mid] == key)
        return key;
      else if(arr[mid] > key)
      {
        auto diff = std::abs(arr[mid] - key);
        if(diff < minDiff.first)
        {
          minDiff.first = diff;
          minDiff.second = arr[mid];
        }
        end = mid - 1;
      }
      else
      {
        auto diff = std::abs(arr[mid] - key);
        if(diff < minDiff.first)
        {
          minDi

P

Pete Stenger

· 2 years ago

class Solution:
  def searchMinDiffElement(self, arr, key):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
      mid = (lo + hi) // 2
      if arr[mid] == key:
        return arr[mid]
      elif arr[mid] < key:
        lo = mid + 1
      else:
        hi = mid - 1
    
    # lo holds idx right after
    after = math.inf if lo >= len(arr) else arr[lo]
    # hi holds idx right before
    before = -math.inf if hi < 0 else arr[hi]
    
    if after - key < key - before:
      return after
    else:
      return before

Gustavo Alves

· 8 months ago