0% completed

Minimum Difference Element (medium)

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

Try it yourself

Try solving this question here:

.....

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

· 9 months ago