CareerCup

Perform a binary search of K on the array and from that iterate over until we get the all the C closest elements. The cost is log(n) + C. By the way the solution for the example should be 5 isn't?
Solution in Python

def closest_to_K(seq, K, C):
    lo, hi = 0, len(seq) - 1
    value = 0
    while lo < hi:
        mid = (lo  + hi) / 2
        if seq[mid] == K:
            value = mid
            break
        elif seq[mid] > K:
            hi = mid - 1
        else:
            lo = mid + 1
    
    if lo >= hi: value = lo # In case K is not in the array
    res = []
    lo, hi = value, value + 1
    if seq[value] == K:
        res.append(K)
        lo, hi = value - 1, value + 1
    while len(res) != C:
        if K - seq[lo] <= seq[hi] - K:
            res.insert(0, seq[lo])
            lo -= 1
        else:
            res.append(seq[hi])
            hi += 1
    
    return res[0]

In: closest_to_K([1,2,5,8,9,13], 8, 4)
Out: 5

In: closest_to_K([1,2,5,8,9,13], 7, 4)
Out: 2

Edit: Added some examples

An suboptimal/optimal solution in O((log(n))^2) is:
1. Find position of K by using binary search in log(n) time
2. Do a nested binary search inside binary search to find L.
Binary search for radius (low_radius, high_radius) around key K:
- Binary search for number of elements on the left of K
- Binary search for number of elements on the right of K
- Total = number elements from left + number of elements from right + 1
If total >= C we binary search on (low_radius, mid_radius), otherwise we binary search on (mid_radius+1, high_radius).
Full code:

int bs(int A[],int low,int high,int value){
  if(low==high)
    return low;
  int mid = (low+high)/2;
  if(A[mid]>=value)
    return bs(A,low,mid,value);
  return bs(A,mid+1,high,value);
}

int bsR(int A[],int lowR,int highR,int C,int K,int index){
  if(lowR == highR){
    if(index-1<0)
      return index;
    int left = C-lowR;
    int leftIndex =  bs(A,0,index-1,left);
    if(A[leftIndex]>=left)
      return leftIndex;
    return index;
  }
  int midR = (lowR+highR)/2;
  int right = C + midR;
  int left = C - midR;
  
  int nLeft = 0;
  if(index-1>=0){
    int leftIndex = bs(A,0,index-1,left);
    if(A[leftIndex]>=left)
      nLeft = index-leftIndex;
  }

  int nRight = 0;
  if(index+1<=n-1){
    int rightIndex = bs(A,index+1,n-1,right+1);
    if(A[rightIndex]<=right){
      nRight = rightIndex - index;
    }
    else{
      if(rightIndex>index+1){
        nRight = rightIndex - 1 - index;
      }
    }
  }
 
  int n = 1 + nLeft + nRight;
  if(n>=K)
    return bsR(A,lowR,midR,C,K,index);
  return bsR(A,midR+1,highR,C,K,index);
}

int kClosest(int A[],int n,int C,int K){
  int index = bs(A,0,n-1,C);
  int r = max(A[n-1]-C,C-A[0]);
  return bsR(A,0,r,C,K,index);
}

int Leftindex(vector<int> A, int K, int C)
{
    // 1. apply the b-search to find the index of closest point to K
    int b=0, e=A.size()-1, mid;
    while(b<=e)
    {
        mid = (b+e)/2;
        if(K==A[mid])
            break;
        if(K>A[mid]) b = mid+1;
        else e = mid-1;
    }
    // 2. do the expansion
    b = e = mid;
    while(e-b<C-1)
    {
        if(K-A[b-1]>A[e+1]-K) e++;
        else b--;
    }
    return b;
}

public static int SearchRange(int[] array,int key,int K){
		//List<Integer> list = new ArrayList<>();
		if(K>=array.length){
			return 0;
		}
		int index = Arrays.binarySearch(array,key);
		if(index<0){
			index = -(index+1);
		}
		int left=index-1;
		int right=index;
		int count=0;
		while(count<K){
			Integer left_value=left>=0?array[left]:null;
			Integer right_value=right<array.length?array[right]:null;
            if(left_value==null){
            	right++;
            }else if(right_value==null){
            	left--;
            }else if(Math.abs(key-left_value)<Math.abs(key-right_value)){
            	left--;
            }else{
            	right++;
            }
			count++;
		}
		return left+1;
	}

public class Range {
    public static void main(String... a) {
        int[] arr = {1, 2, 5, 8, 9, 13};
//        int[] arr = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
        int ele = 8;
        int rangeSize = 4;

        findRange(arr, ele, rangeSize);
    }

    private static void findRange(int[] arr, int ele, int rangeSize) {
        int mid = bsearch(arr, ele);
        expand(arr, mid, rangeSize);
    }

    private static int bsearch(int[] arr, int ele) {
        int low = 0;
        int high = arr.length;
        int mid = -1;
        while (low <= high) {
            mid = (high - low) / 2;
            if (arr[mid] == ele) {
                break;
            } else if (arr[mid] < ele) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return mid;
    }

    private static void expand(int[] arr, int loc, int rangeSize) {
        int end = loc + 1;
        int start = loc - 1;
        System.out.print(arr[loc] + "  ");
        for (int i = 0; i < rangeSize - 1; ++i) {
            if (arr[loc] - arr[start] > arr[end] - arr[loc]) {
                System.out.print(arr[end] + "  ");
                ++end;
            } else {
                System.out.print(arr[start] + "  ");
                --start;
            }
        }
    }
}

Solution: O(logn) + O(C)

-> binary search over n to find closest element to K
-> L=closest, R=closest
-> while (R-L+1 < C):
-> if (| array[L-1] - K |<=| array[R+1]) - K |:
-> L=L-1
-> else:
-> R=R+1
->return L

the follow-up will be how to optimize the linear time for selecting C element (if C is big for example) ... you can get to O(lg(n)+lg(C))

int FindBlock(vector<int> const &a, int n, int block_size)
{
	int result = -1;

	if (block_size > 0 &&
		a.size() >= block_size)
	{
		int n_idx = -1;
		int l = 0;
		int r = a.size() - 1;
		while (l <= r &&
			n_idx == -1)
		{
			int mid = (l + r) / 2;
			if (a[mid] == n) {
				n_idx = mid;
			} else if (a[mid] > n) {
				r = (r == mid) ? r - 1 : mid;
			} else {
				l = (l == mid) ? l + 1 : mid;
			}
		}
		
		if (n_idx != -1) {
			int l = n_idx;
			int r = n_idx;
			while (r - l + 1 < block_size) {
				if (l == 0) {
					++r;
				} else if (r == a.size() - 1) {
					--l;
				} else {
					if (n - a[l - 1] < a[r + 1] - n) {
						--l;
					} else {
						++r;
					}
				}
			}
			result = l;
		}
	}

	return result;
}

import operator
def closest_to_k(A,k,c):
      d = {}
      for i in range(len(A)):
            d[i] = abs(A[i]-k)
      sorted_x = sorted(d.items(), key=operator.itemgetter(1))
      count = 1
      min_ind = sorted_x[1][0]
      while (count < c):    
             if(sorted_x[count][0] < min_ind):
                   min_ind = sorted_x[count][0]
             count+=1   
    
  return (min_ind,A[min_ind:min_ind+c])

If C (n in my code) is small (say, C <= 32), just do a linear search. Otherwise, do a binary search:

inline constexpr std::ptrdiff_t n_threshold = 32;

template<class Random_access_it>
std::pair<Random_access_it, Random_access_it> closest_elements1(
	Random_access_it first, Random_access_it last, Random_access_it pos, std::ptrdiff_t n) {
	if (first == last || n <= 0)
		return {pos, pos};

	auto left = pos;
	auto right = pos + 1;

	while (--n > 0 && left != first && right != last)
		if (*right - *pos < *pos - *(left - 1))
			++right;
		else
			--left;

	if (left == first)
		right += std::min(n, last - right);
	if (right == last)
		left -= std::min(n, left - first);

	return {left, right};
}

template<class Random_access_it>
std::pair<Random_access_it, Random_access_it> closest_elements2(
	Random_access_it first, Random_access_it last, Random_access_it pos, std::ptrdiff_t n) {
	if (first == last || n <= 0)
		return {pos, pos};
	if (last - first <= n)
		return {first, last};

	auto left = first + std::max(std::ptrdiff_t{0}, (pos - first) - (n - 1));
	auto right = pos - std::max(std::ptrdiff_t{0}, n - (last - pos));

	while (left != right)
		if (const auto mid = left + (right - left) / 2; *(mid + n) - *pos < *pos - *mid)
			left = mid + 1;
		else
			right = mid;

	return {left, left + n};
}

template<class Random_access_it, class T>
std::pair<Random_access_it, Random_access_it> closest_elements(
	Random_access_it first, Random_access_it last, const T& value, std::ptrdiff_t n) {
	if (n <= n_threshold) {
		const auto pos = std::find(first, last, value);
		return closest_elements1(first, last, pos, n);
	} else {
		const auto pos = std::lower_bound(first, last, value);
		return closest_elements2(first, last, pos, n);
	}
}

def nearestCElem2K(list, K, C):
    pos = binarySearch(list, K);
    op = []
    opIndex=999999;
    i = pos - 1;
    j = pos;
    count = 0;
    while count < C and i >= 0 and j < len(list):
          if abs(list[i] - K) < abs(list[j] - K):
             op.append(list[i]);
             opIndex=min(i,opIndex); 
             i = i - 1; 
          else:
             op.append(list[j]);  
             j = j + 1;
          count = count + 1;
          
    while count < C and i >= 0:
          op.append(list[i]);
          opIndex=min(i,opIndex);
          i = i - 1;
          count = count + 1; 
    while count < C and j < len(list):
          op.append(list[j]);
          j = j + 1;
          count = count + 1;
    print(op);                          
    return list[opIndex];

def binarySearch(list, K):
    st = 0;
    end = len(list) - 1;
    while st < end:
          mid = st + ((end - st) / 2);
          if list[mid] == K:
             return mid;
          if list[mid] < K:
             st = mid + 1;
          else:
             end = mid - 1;      
    return st;          
 
print(nearestCElem2K([1,2,5,8,9,13],8,4));

- Linear search finding begin and end index for values who lies within [K-C, K+C]
- Since data is sorted we can use binary search to find begin/end index of values that lies within [K-C, K+C]