Given an array of sorted integers. The task is to find the closest value to the given number in array. Array may contain duplicate values.
Note: If the difference is same for two values print the value which is greater than the given number.
Example 1:
Input : Arr[] = {1, 3, 6, 7} and K = 4
Output : 3
Explanation:
We have an array [1, 3, 6, 7] and target is 4.
If we look at the absolute difference of target 
with every element of an array we will 
get [ |1-4|, |3-4|, |6-4|, |7-4| ]. 
So, the closest number is 3.
Example 2:
Input : Arr[] = {1, 2, 3, 5, 6, 8, 9}, K = 4
Output : 5
 
Your Task:
This is a function problem. The input is already taken care of by the driver code. You only need to complete the function findClosest() that takes an array (arr), sizeOfArray (n), integer target and return the closest number of the target in an array. The driver code takes care of the printing.
Expected Time Complexity: O(log(N)).
Expected Auxiliary Space: O(1).
 
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ K ≤ 10^{5}
1 ≤ A[i] ≤ 10^{5}

Difficulty: EASY
Tags: Sorting

Data structures
Skill types: Sorting

Data structures
Expected Time Complexity: O(log(N)).
Expected Auxiliary Space: O(1).

Starter code:
#User function Template for python3



class Solution:

    def findClosest(self, arr, n, target): 

      

        # Complete the function

Solutions:
class Solution:

	def findClosest(self, arr, n, target):
		h_a = [0] * n
		for i in range(n):
			h_a[i] = abs(arr[i] - target)
		m = min(h_a)
		for i in range(-1, n * -1, -1):
			if h_a[i] == m:
				return arr[i]
		return arr[0]


class Solution:

	def findClosest(self, arr, n, target):
		difference = abs(arr[0] - target)
		number = 0
		for i in range(0, len(arr)):
			if abs(arr[i] - target) < difference or (arr[i] - target == difference and arr[i] > arr[number]):
				difference = abs(arr[i] - target)
				number = i
		return arr[number]


class Solution:

	def findClosest(self, arr, n, target):
		d = {}
		for i in arr:
			d[i] = abs(i - target)
		l = []
		for i in sorted(d.values()):
			for j in d:
				if d[j] == i:
					l.append(j)
			break
		return max(l)


import math

class Solution:

	def findClosest(self, arr, n, target):
		diff = 1000000
		for i in arr:
			temp = abs(i - target)
			if temp <= diff:
				diff = temp
				ans = i
		return ans


class Solution:

	def findClosest(self, arr, n, target):
		b = abs(arr[0] - target)
		j = 0
		for i in arr:
			c = abs(target - i)
			if c <= b:
				b = c
				j = i
		return j


class Solution:

	def findClosest(self, arr, n, target):
		c = abs(arr[0] - target)
		ind = 0
		for i in range(1, n):
			if abs(arr[i] - target) <= c:
				c = abs(arr[i] - target)
				ind = i
		return arr[ind]


def closest(arr, target, i, shift):
	j = i + shift
	if j < 0 or j >= len(arr):
		return i
	di = abs(arr[i] - target)
	dj = abs(arr[j] - target)
	if di == dj and arr[i] >= arr[j]:
		return i
	if di == dj and arr[j] >= arr[i]:
		return j
	if di < dj:
		return i
	if dj < di:
		return j
	return j

def bin_search_closest(arr, target):
	start = 0
	end = len(arr)
	while start < end:
		mid = start + (end - start) // 2
		if arr[mid] == target:
			return mid
		elif arr[mid] < target:
			c = closest(arr, target, mid, 1)
			start = mid + 1
		else:
			c = closest(arr, target, mid, -1)
			end = mid
	return c

class Solution:

	def findClosest(self, arr, n, target):
		i = bin_search_closest(arr, target)
		return arr[i]


class Solution:

	def findClosest(self, arr, n, target):
		diff = abs(arr[0] - target)
		number = 0
		for i in range(n):
			ab = abs(arr[i] - target)
			if ab <= diff:
				diff = ab
				number = arr[i]
		return number


class Solution:

	def findClosest(self, arr, n, k):
		min = arr[0]
		val = 0
		for i in arr:
			if i - k <= min:
				min = abs(i - k)
				val = i
		return val


class Solution:

	def findClosest(self, arr, n, target):
		val = arr[0]
		mindiff = abs(val - target)
		for i in arr:
			diff = abs(i - target)
			if diff < mindiff or (diff == mindiff and i > val):
				val = i
				mindiff = diff
		return val


class Solution:

	def findClosest(self, arr, n, target):
		min = 1000000
		for i in arr:
			diff = abs(target - i)
			if diff < min:
				min = diff
				result = i
			elif diff == min and i > target:
				result = i
		return result


class Solution:

	def findClosest(self, arr, n, t):
		s = 0
		e = n - 1
		res = arr[0]
		if t < arr[0]:
			return arr[0]
		elif t > arr[n - 1]:
			return arr[n - 1]
		while s <= e:
			m = (s + e) // 2
			if t == arr[m]:
				return arr[m]
			elif t < arr[m]:
				e = m - 1
			else:
				s = m + 1
		if s == 0:
			return arr[0]
		elif e == n - 1:
			return arr[n - 1]
		elif abs(arr[s] - t) <= abs(t - arr[e]):
			res = arr[s]
		else:
			res = arr[e]
		return res


class Solution:

	def findClosest(self, arr, n, target):
		arr = sorted(arr, key=lambda x: (abs(x - target), -x))
		return arr[0]


class Solution:

	def findClosest(self, arr, n, target):
		f = 0
		l = len(arr) - 1
		while f <= l:
			mid = f + (l - f) // 2
			if target == arr[mid]:
				return arr[mid]
			elif target < arr[mid]:
				l = mid - 1
			else:
				f = mid + 1
		if f == 0:
			return arr[0]
		elif l == len(arr) - 1:
			return arr[n - 1]
		else:
			diffleft = abs(arr[f] - target)
			diffright = abs(arr[l] - target)
			if diffleft <= diffright:
				return arr[f]
			else:
				return arr[l]


import math

class Solution:

	def findClosest(self, arr, n, target):
		mini = math.inf
		maxi = -math.inf
		left = 0
		right = n - 1
		while left <= right:
			mid = (left + right) // 2
			if abs(arr[mid] - target) < mini:
				mini = min(mini, abs(arr[mid] - target))
				maxi = arr[mid]
			elif abs(arr[mid] - target) == mini:
				maxi = max(maxi, arr[mid])
			if arr[mid] > target:
				right = mid - 1
			elif arr[mid] < target:
				left = mid + 1
			else:
				return arr[mid]
		return maxi


class Solution:

	def findClosest(self, arr, n, target):
		if target <= arr[0]:
			return arr[0]
		if target >= arr[n - 1]:
			return arr[n - 1]

		def getsmaller(s, l, t):
			if abs(t - l) == abs(t - s):
				return l
			if abs(t - l) > abs(t - s):
				return s
			else:
				return l
		start = 0
		end = n - 1
		mid = 0
		while start <= end:
			mid = (start + end) // 2
			if arr[mid] == target:
				return arr[mid]
			if target < arr[mid]:
				if mid > 0 and target > arr[mid - 1]:
					return getsmaller(arr[mid - 1], arr[mid], target)
				end = mid
			if target > arr[mid]:
				if mid < end and target < arr[mid + 1]:
					return getsmaller(arr[mid], arr[mid + 1], target)
				start = mid + 1
		return arr[mid]


class Solution:

	def findClosest(self, arr, n, target):
		left = 0
		right = len(arr) - 1
		closest = None
		while left <= right:
			mid = (left + right) // 2
			if arr[mid] == target:
				return arr[mid]
			elif arr[mid] > target:
				right = mid - 1
			else:
				left = mid + 1
			if closest is None or abs(arr[mid] - target) < abs(closest - target) or (abs(arr[mid] - target) == abs(closest - target) and arr[mid] > closest):
				closest = arr[mid]
		return closest


class Solution:

	def findClosest(self, arr, n, k):
		if k in arr:
			return k
		arr = list(set(arr))
		d = {}
		l = []
		for i in arr:
			d[i] = abs(i - k)
		s = sorted(d.items(), key=lambda x: x[1])
		m = s[0][1]
		ans = s[0][0]
		l = []
		for i in s:
			if i[1] <= m:
				l.append(i[0])
		return max(l)


class Solution:

	def findClosest(self, arr, n, target):
		mini = target
		value = 0
		for i in arr:
			if i - target <= mini:
				mini = abs(i - target)
				value = i
		if value != 0:
			return value
		else:
			return arr[0]


class Solution:

	def findClosest(self, arr, n, target):
		l = []
		for i in range(n):
			l.append(abs(arr[i] - target))
		min_l = min(l)
		ansi = 0
		for i in range(len(l)):
			if l[i] == min_l:
				ansi = i
		return arr[ansi]


class Solution:

	def findClosest(self, arr, n, target):
		(min, val) = (target, 0)
		for i in arr:
			if i - target <= min:
				(min, val) = (abs(i - target), i)
		return val if val != 0 else arr[0]


class Solution:

	def findClosest(self, arr, n, target):
		c = arr[0]
		diff = abs(c - target)
		for i in arr:
			if abs(i - target) <= diff and i > c:
				diff = abs(i - target)
				c = i
		return c


class Solution:

	def findClosest(self, arr, n, target):
		low = 0
		high = n - 1
		ans = 1000000000.0
		while low <= high:
			mid = (low + high) // 2
			if arr[mid] == target:
				return arr[mid]
			elif arr[mid] > target:
				if abs(arr[mid] - target) < abs(ans - target):
					ans = arr[mid]
				elif abs(arr[mid] - target) == abs(ans - target) and ans < arr[mid]:
					ans = arr[mid]
				high = mid - 1
			else:
				if abs(arr[mid] - target) < abs(ans - target):
					ans = arr[mid]
				elif abs(arr[mid] - target) == abs(ans - target) and ans < arr[mid]:
					ans = arr[mid]
				low = mid + 1
		return ans


class Solution:

	def findClosest(self, arr, n, target):
		start = 0
		end = n - 1
		diff = 10000000000000
		val = 0
		if n == 1:
			return arr[0]
		while start <= end:
			mid = int((start + end) / 2)
			diff1 = abs(target - arr[mid])
			if target > arr[mid]:
				start = mid + 1
				if diff1 < diff:
					diff = diff1
					val = arr[mid]
			elif target < arr[mid]:
				end = mid - 1
				if diff1 <= diff:
					diff = diff1
					val = arr[mid]
			else:
				return arr[mid]
		return val


class Solution:

	def findClosest(self, arr, n, target):
		if target <= arr[0]:
			return arr[0]
		if target >= arr[n - 1]:
			return arr[n - 1]
		(low, high) = (0, n - 1)
		while low <= high:
			mid = (low + high) // 2
			if arr[mid] == target:
				return arr[mid]
			elif arr[mid] < target:
				low = mid + 1
			else:
				high = mid - 1
		if abs(arr[low] - target) < abs(arr[high] - target):
			return arr[low]
		elif abs(arr[low] - target) > abs(arr[high] - target):
			return arr[high]
		else:
			return max(arr[low], arr[high])


class Solution:

	def findClosest(self, arr, n, target):
		val = arr[0]
		md = abs(val - target)
		for i in arr:
			d = abs(i - target)
			if d < md or (d == md and i > val):
				val = i
				md = d
		return val


def get_closest(a, b, c):
	if abs(a - c) >= abs(b - c):
		return b
	else:
		return a

class Solution:

	def findClosest(self, arr, n, target):
		if target >= arr[-1]:
			return arr[-1]
		if target <= arr[0]:
			return arr[0]
		lo = 0
		hi = n - 1
		best = lo
		while lo < hi:
			mid = (lo + hi) // 2
			if arr[mid] == target:
				return arr[mid]
			elif arr[mid] > target:
				if arr[mid - 1] <= target:
					return get_closest(arr[mid - 1], arr[mid], target)
				hi = mid - 1
			else:
				if arr[mid + 1] >= target:
					return get_closest(arr[mid], arr[mid + 1], target)
				lo = mid + 1


class Solution:

	def bsf(self, arr, k):
		(l, h, ans) = (0, len(arr) - 1, -1)
		while l <= h:
			m = (l + h) // 2
			if arr[m] > k:
				h = m - 1
			else:
				ans = arr[m]
				l = m + 1
		return ans

	def bsc(self, arr, k):
		(l, h, ans) = (0, len(arr) - 1, -1)
		while l <= h:
			m = (l + h) // 2
			if arr[m] < k:
				l = m + 1
			else:
				ans = arr[m]
				h = m - 1
		return ans

	def findClosest(self, arr, n, target):
		if n == 1:
			return arr[0]
		(f, l) = (self.bsf(arr, target), self.bsc(arr, target))
		if f != -1 and l == -1:
			return f
		elif f == -1 and l != -1:
			return l
		(t1, t2) = (abs(f - target), abs(l - target))
		if t1 < t2:
			return f
		elif t1 == t2 or t2 < t1:
			return l


from bisect import bisect_left

class Solution:

	def findClosest(self, arr, n, k):
		(min, val) = (k, 0)
		for i in arr:
			if i - k <= min:
				(min, val) = (abs(i - k), i)
		return val if val != 0 else arr[0]


class Solution:

	def findClosest(self, arr, n, target):
		mini = 999999
		res = 0
		for i in arr:
			if abs(i - target) <= mini:
				mini = abs(i - target)
				res = i
		return res


class Solution:

	def findClosest(self, arr, n, target):
		a = 0
		b = 0
		for i in range(n):
			if arr[i] < target:
				a = arr[i]
				continue
		for j in range(n):
			if arr[j] > target:
				b = arr[j]
				break
		x = target - a
		y = b - target
		if target in arr:
			return target
		elif arr[n - 1] < target:
			return arr[n - 1]
		elif arr[0] > target:
			return arr[0]
		elif x > y:
			return b
		elif x == y:
			return b
		else:
			return a


def binarySearch(arr, n, k):
	(l, r, mid) = (0, n - 1, 0)
	while l <= r:
		mid = (l + r) // 2
		if arr[mid] < k:
			l = mid + 1
		elif arr[mid] > k:
			r = mid - 1
		else:
			return k
	if l >= n or r >= n:
		return arr[-1]
	(vl, vr) = (arr[l], arr[r])
	m1 = abs(vl - k)
	m2 = abs(vr - k)
	if m1 < m2:
		return vl
	if m1 > m2:
		return vr
	else:
		return max(vl, vr)

class Solution:

	def findClosest(self, arr, n, target):
		return binarySearch(arr, n, target)


class Solution:

	def findClosest(self, arr, n, target):
		val = abs(arr[0] - target)
		ans = arr[0]
		for i in range(1, n):
			temp = abs(arr[i] - target)
			if temp <= val:
				val = temp
				ans = arr[i]
		return ans


from bisect import bisect_left

class Solution:

	def findClosest(self, arr, n, target):
		k = bisect_left(arr, target, 0, n)
		if k == 0:
			return arr[0]
		if k == n:
			return arr[-1]
		return arr[k] if arr[k] - target <= target - arr[k - 1] else arr[k - 1]


class Solution:

	def findClosest(self, arr, n, k):
		a = []
		for i in arr:
			diff = k - i
			if diff < 0:
				diff *= -1
			a.append(diff)
		min1 = min(a)
		a1 = []
		for i in range(0, n):
			if min1 == a[i]:
				a1.append(arr[i])
		return max(a1)


class Solution:

	def findClosest(self, arr, n, target):
		k = []
		for i in range(n):
			d = abs(target - arr[i])
			k.append(d)
		k.sort()
		if k[0] + target in arr:
			return k[0] + target
		else:
			return target - k[0]


import math

class Solution:

	def findClosest(self, arr, n, target):
		m = target - arr[0]
		for i in arr:
			if math.fabs(i - target) <= m:
				m = target - i
			else:
				return target - m
		return target - m


import sys

class Solution:

	def findClosest(self, arr, n, target):
		mdiff = sys.maxsize
		ind = 0
		for i in range(n):
			d = abs(target - arr[i])
			if d < mdiff:
				mdiff = d
				ind = i
			elif d == mdiff:
				ind = i
			else:
				continue
		return arr[ind]


class Solution:

	def findClosest(self, arr, n, k):
		min1 = k
		val = 0
		for i in arr:
			if i - k <= min1:
				val = i
				min1 = abs(i - k)
		return val if val != 0 else arr[0]


class Solution:

	def findClosest(self, arr, n, target):
		i = 0
		j = n - 1
		if arr[i] >= target:
			return arr[i]
		if arr[j] <= target:
			return arr[j]
		mid = i + (j - i) // 2
		while i <= j:
			if arr[mid] > target:
				j = mid - 1
			elif arr[mid] < target:
				i = mid + 1
			if arr[mid] == target:
				return arr[mid]
			mid = i + (j - i) // 2
		if abs(target - arr[i]) <= abs(arr[j] - target):
			return arr[i]
		else:
			return arr[j]


class Solution:

	def findClosest(self, arr, n, target):
		dict1 = {}
		lst = []
		for i in arr:
			dict1[i] = abs(i - target)
		mini = min(dict1.values())
		for i in dict1:
			if dict1[i] == mini:
				lst.append(i)
		if len(lst) == 1:
			return lst[0]
		else:
			return max(lst)


class Solution:

	def findClosest(self, arr, n, target):
		d = {}
		for i in range(0, n):
			d[arr[i]] = abs(arr[i] - target)
		temp = min(d.values())
		l = [i for i in d if d[i] == temp]
		return max(l)


class Solution:

	def findClosest(self, arr, n, target):
		diff = 100000
		ans = 0
		l = 0
		h = n - 1
		while l <= h:
			mid = (l + h) // 2
			if arr[mid] < target:
				l = mid + 1
				if diff > abs(arr[mid] - target):
					diff = abs(arr[mid] - target)
					ans = arr[mid]
			elif arr[mid] > target:
				if diff >= abs(arr[mid] - target):
					diff = abs(arr[mid] - target)
					ans = arr[mid]
				h = mid - 1
			else:
				return arr[mid]
		return ans


from collections import OrderedDict

class Solution:

	def findClosest(self, arr, n, target):
		dict = OrderedDict()
		for i in arr:
			if i in dict:
				dict[i] = abs(target - i)
			else:
				dict[i] = abs(target - i)
		mini = 10 ** 5
		k = target
		for j in dict:
			if dict[j] <= mini:
				mini = dict[j]
				k = j
		return k


class Solution:

	def findClosest(self, arr, n, target):
		min_diff = float('inf')
		min_val = float('inf')
		for elem in arr:
			current_diff = abs(elem - target)
			(min_diff, min_val) = (current_diff, elem) if current_diff <= min_diff else (min_diff, min_val)
		return min_val


class Solution:

	def findClosest(self, arr, n, target):
		min_diff = float('inf')
		min_val = float('inf')
		for elem in arr:
			data = abs(elem - target)
			if data < min_diff:
				min_diff = data
				min_val = elem
			elif data == min_diff:
				min_val = elem
		return min_val


class Solution:

	def findClosest(self, arr, n, target):
		arr = list(set(arr))
		n = len(arr)
		dict = {}
		for i in range(0, n):
			dict[arr[i]] = abs(arr[i] - target)
		temp = min(dict.values())
		l = [i for i in dict if dict[i] == temp]
		return max(l)


class Solution:

	def findClosest(self, arr, n, target):
		l = []
		for i in arr:
			l.append(abs(i - target))
		m = min(l)
		l1 = []
		for i in range(len(l)):
			if l[i] == m:
				l1.append(arr[i])
		if len(l1) == 1:
			return l1[0]
		else:
			return l1[-1]


class Solution:

	def findClosest(self, arr, n, target):
		d = {}
		for i in arr:
			x = abs(target - i)
			if i in d:
				d[i] = x
			else:
				d[i] = x
		min = 9999999
		c = -1
		for i in d:
			if d[i] < min:
				min = d[i]
		for i in d:
			if d[i] == min and i > c:
				c = i
		return c


class Solution:

	def findClosest(self, arr, n, k):
		d = {}
		for i in arr:
			if abs(i - k) not in d:
				d[abs(i - k)] = [i]
			else:
				d[abs(i - k)].append(i)
		return d[min(d.keys())][-1]


class Solution:

	def findClosest(self, a, n, k):
		dic = {}
		for i in a:
			if abs(i - k) not in dic:
				dic[abs(i - k)] = [i]
			else:
				dic[abs(i - k)].append(i)
		return dic[min(dic.keys())][-1]


class Solution:

	def findClosest(self, arr, n, target):
		min = float('inf')
		for i in range(n):
			val = abs(arr[i] - target)
			if val <= min:
				min = val
				res = arr[i]
		return res


class Solution:

	def findClosest(self, arr, n, target):
		import math
		arr.sort()
		r = math.fabs(target - arr[n - 1])
		c = arr[n - 1]
		for i in range(n - 2, -1, -1):
			if math.fabs(target - arr[i]) < r:
				r = math.fabs(target - arr[i])
				c = arr[i]
		return c


def Search(arr, ele):
	if ele > arr[-1]:
		return arr[-1]
	if ele < arr[0]:
		return arr[0]
	(i, j) = (0, len(arr) - 1)
	while i <= j:
		mid = (i + j) // 2
		if arr[mid] == ele:
			return ele
		elif arr[mid] > ele:
			j = mid - 1
		else:
			i = mid + 1
	smaller = abs(arr[j] - ele)
	grater = abs(arr[i] - ele)
	if smaller == grater:
		return arr[i]
	if smaller < grater:
		return arr[j]
	return arr[i]

class Solution:

	def findClosest(self, arr, n, target):
		return Search(arr, target)


class Solution:

	def findClosest(self, arr, n, target):
		diff = float('inf')
		index = -1
		for i in range(n):
			d = abs(arr[i] - target)
			if d == 0:
				return target
			elif diff > d:
				diff = d
				index = i
			elif diff == d and arr[i] > target:
				diff = d
				index = i
		return arr[index]


class Solution:

	def findClosest(self, arr, n, target):
		i = 0
		if target in arr:
			return target
		elif target > arr[-1]:
			return arr[-1]
		elif target < arr[0]:
			return arr[0]
		else:
			while arr[i] <= target:
				i += 1
			arr1 = arr[:i]
			arr2 = arr[i:]
			min = arr2[0] - target
			if target - arr1[-1] < min:
				return arr1[-1]
			else:
				return arr2[0]


class Solution:

	def findClosest(self, arr, n, target):
		j = 0
		while j < n and arr[j] < target:
			j += 1
		if j == n:
			return arr[n - 1]
		if arr[j] == target:
			return arr[j]
		if j == 0:
			return arr[0]
		if arr[j] - target > target - arr[j - 1]:
			return arr[j - 1]
		return arr[j]


import sys

class Solution:

	def findClosest(self, arr, n, target):
		diff = sys.maxsize
		ans = 0
		for i in arr:
			if abs(target - i) < diff:
				ans = i
				diff = abs(target - i)
			elif abs(target - i) == diff and i > ans:
				ans = i
		return ans


class Solution:

	def findClosest(self, arr, n, target):
		if target in arr:
			return target
		arr = list(set(arr))
		dic = {}
		lis = []
		for i in arr:
			dic[i] = abs(i - target)
		s = sorted(dic.items(), key=lambda x: x[1])
		m = s[0][1]
		ans = s[0][0]
		l = []
		for i in s:
			if i[1] <= m:
				l.append(i[0])
		return max(l)


class Solution:

	def findClosest(self, arr, n, k):
		left = 0
		right = n - 1
		diff = 100001
		closest = -1
		while right >= left:
			mid = int((left + right) / 2)
			if arr[mid] > target:
				if diff > abs(arr[mid] - target):
					closest = arr[mid]
					diff = abs(arr[mid] - target)
				elif diff == abs(arr[mid] - target):
					closest = max(arr[mid], closest)
				right = mid - 1
			elif arr[mid] == target:
				closest = arr[mid]
				break
			else:
				if diff > abs(arr[mid] - target):
					closest = arr[mid]
					diff = abs(arr[mid] - target)
				elif diff == abs(arr[mid] - target):
					closest = max(arr[mid], closest)
				left = mid + 1
		return closest


class Solution:

	def findClosest(self, arr, n, target):
		l2 = []
		l3 = []
		for i in arr:
			diff = abs(i - target)
			l2.append(diff)
		l2_min = min(l2)
		for i in range(len(l2)):
			if l2[i] == l2_min:
				l3.append(arr[i])
		return max(l3)


class Solution:

	def findClosest(self, arr, n, target):
		dic = {}
		for i in arr:
			dic[i] = abs(target - i)
			if dic[i] == 0:
				return i
		k = min(dic.values())
		a = []
		for (i, j) in dic.items():
			if j == k:
				a += [i]
		return max(a)


class Solution:

	def findClosest(self, arr, n, target):
		ans = 9999999
		res = 0
		for i in range(n):
			if ans >= abs(arr[i] - target):
				ans = abs(arr[i] - target)
				res = arr[i]
		return res


class Solution:

	def findClosest(self, arr, n, target):
		if n == 1:
			return arr[0]
		closest = 1000000
		numbers = []
		for number in set(arr):
			if abs(number - target) <= closest:
				numbers.append(number)
				closest = abs(number - target)
		return numbers[-1]


class Solution:

	def findClosest(self, arr, n, target):
		l = -1
		r = n
		while l + 1 < r:
			mid = l + (r - l) // 2
			if self.predicate(arr, mid, target) == 0:
				l = mid
			else:
				r = mid
		if l == -1 and r == 0:
			return arr[0]
		elif l == n - 1 and r == n:
			return arr[n - 1]
		if target - arr[l] < arr[r] - target:
			return arr[l]
		else:
			return arr[r]

	def predicate(self, arr, mid, target):
		if arr[mid] < target:
			return 0
		else:
			return 1


class Solution:

	def findClosest(self, arr, n, target):
		A = []
		for i in arr:
			A.append(abs(i - target))
		A.sort()
		if A[0] + target in arr:
			return A[0] + target
		else:
			return target - A[0]


class Solution:

	def findClosest(self, a, n, t):
		close = 100000007
		num = -1
		for i in range(len(a)):
			if abs(a[i] - t) <= close:
				close = abs(a[i] - t)
				num = a[i]
		return num


class Solution:

	def findClosest(self, arr, n, target):
		dic = {}
		for i in range(len(arr)):
			dic[arr[i]] = abs(target - arr[i])
		x = [x1 for x1 in dic.values()]
		x1 = min(x)
		x2 = [x3 for x3 in dic.keys() if dic[x3] == x1]
		if len(x2) == 1:
			return x2[0]
		else:
			return max(x2)


import sys

class Solution:

	def findClosest(self, arr, n, target):
		if n == 1:
			return arr[0]
		n = len(arr)
		(start, end) = (0, n - 1)
		while start <= end:
			mid = start + (end - start) // 2
			if arr[mid] == target:
				return target
			elif target > arr[mid]:
				start = mid + 1
			else:
				end = mid - 1
		if start == n:
			return arr[end]
		elif end < 0:
			return arr[start]
		else:
			diff_with_start = abs(arr[start] - target)
			diff_with_end = abs(arr[end] - target)
			if diff_with_start < diff_with_end:
				return arr[start]
			elif diff_with_start > diff_with_end:
				return arr[end]
			else:
				return max(arr[start], arr[end])


class Solution:

	def findClosest(self, arr, n, target):
		arr.append(target)
		arr.sort()
		index = arr.index(target)
		if index == 0:
			return arr[index + 1]
		elif index == n:
			return arr[index - 1]
		else:
			diff1 = arr[index + 1] - target
			diff2 = target - arr[index - 1]
			if diff1 > diff2:
				return arr[index - 1]
			else:
				return arr[index + 1]


class Solution:

	def findClosest(self, arr, n, target):
		hash_set = set(arr)
		closest = arr[0]
		min_diff = abs(closest - target)
		for x in hash_set:
			diff = abs(x - target)
			if diff < min_diff:
				closest = x
				min_diff = diff
			elif diff == min_diff and x > closest:
				closest = x
		return closest


class Solution:

	def findClosest(self, arr, n, target):
		(least, val) = (target, 0)
		for num in arr:
			if num - target <= least:
				(least, val) = (abs(num - target), num)
		return val if val != 0 else arr[0]


class Solution:

	def findClosest(self, arr, n, target):
		if target in arr:
			return target
		if target > arr[-1]:
			return arr[-1]
		if target < arr[0]:
			return arr[0]
		else:
			for x in range(n):
				if arr[x] > target:
					if (arr[x - 1] + arr[x]) / 2 == target:
						return arr[x]
					else:
						return arr[x] if abs(target - arr[x - 1]) > abs(target - arr[x]) else arr[x - 1]