Searching: Find the closest number in the sorted array

Problem Statement:

You are given an array, and a value k.

You need to find the the closest value to the number k.

It might have duplicate and -ve value.

Example:

Input : arr[] = {1, 2, 2, 3, 6, 6, 8, 9}, k = 11
Output : 9

9 is closest.

Solution 1: Brute force approach

Traverse the whole array an check how close each element is from the target by comparing the difference.

Keep track of the differences.

Time Complexity: O(n)
Space Complexity: O(1)

Solution 2: Binary search approach

We use binary search in this approach,

Each step we check the mid with the target, if it is closer than the current result, update the result,

Time Complexity: O(log n)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
#include <limits.h>
#include <math.h>

using namespace std;

int solution_1 (vector<int> &arr, int target) 
{

    int result = arr[0];
    for (int i = 1; i < arr.size(); i++) 
    {
      
        if (abs(arr[i] - target) <= abs(result - target)) 
        {
            result = arr[i];
        }
    }
    return result;
}

int solution_2 (vector<int> &arr, int target) 
{
    int result = arr[0];
    int lo = 0, hi = arr.size() - 1;

    while (lo <= hi) 
    {
        int mid = lo + (hi - lo) / 2;

        if (abs(arr[mid] - target) < abs(result - target)) 
        {
            result = arr[mid];
        }
        else if (abs(arr[mid] - target) == abs(result - target)) 
        {
            result = max(result, arr[mid]);
        }

        if (arr[mid] == target) 
        {
            return arr[mid];
        }
        else if (arr[mid] < target) 
        {
            lo = mid + 1;
        }
        else 
        {
            hi = mid - 1;
        }
    }

    return result;
}


int main() 
{
    vector<int> arr = {1, 2, 2, 3, 6, 6, 8, 9};
    int target = 11;
    cout << solution_1(arr, target) << endl;
    cout << solution_2(arr, target) << endl;
    return 0;
}

Output

9
9