Google Interview Question
Software EngineersCountry: India
Interview Type: Phone Interview
public class playGround {
@Test
public void closestNum(){
System.out.println(closest(new int[]{2,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6}, 4));
}
private int closest(int[] input, int target){
if(input.length == 1){
return Math.abs(target - input[0]);
}
if(input.length == 0){
throw new RuntimeException("Input size is 0");
}
int index = helper(input, target, 0, input.length);
return Math.min(Math.abs(target - input[index]), Math.abs(target - input[index-1]));
}
// This function will find the index where input[index] >= target
private int helper(int[] input, int target, int start, int end){
if((end-start) == 1 || (end-start) == 0){
return end;
}
int mid = (start + end) / 2;
if(input[mid] > target){
return helper(input, target, start, mid);
}
else{
return helper(input, target, mid+1, end);
}
}
}
I'ts "just" a binary search. The problem getting binary search correct are:
- it must terminate
- it must work correctly in corner cases
I found it helps to use the notion of loop-invariant, to get it right:
#include <vector>
#include <iostream>
using namespace std;
// returns index to last element in arr that is <= val
// OR if all elements are > val, returns arr.size()
size_t lower_bound_idx(const vector<int>& arr, int val)
{
size_t l = 0;
size_t r = arr.size();
// loop-invariant:
// - [l..r): half open intervale of size >= 1: r-l > 1
// - arr[l] <= val
// - arr[r] > val or r = arr.size()
// the following if ensures loop-invariant of the following while loop.
// i could skip this "if" and let the following while loop return 0, but this would
// violate loop-invariant and make lower_bound behave unexpectedly and
// thus is a nice source for further errors...
if (!(arr[l] <= val)) return arr.size();
while (r - l > 1) {
size_t m = (l + r) / 2;
if (arr[m] <= val) l = m;
else r = m;
}
return l;
}
int find_closest(const vector<int>& arr, int val)
{
if (arr.size() == 0) return -1;
auto i = lower_bound_idx(arr, val);
if (i >= arr.size()) return arr[0]; // indicates arr[0] > val
if (i == arr.size() - 1) return arr.back(); // arr.back() < val
if (val - arr[i] <= arr[i + 1] - val) return arr[i];
return arr[i + 1];
}
int main()
{
cout << (find_closest({ 2,5,6,7,8,8,9 }, 5) == 5) << endl;
cout << (find_closest({ 2,5,6,7,8,8,9 }, 11) == 9) << endl;
cout << (find_closest({ 2,5,6,7,8,8,9 }, 4) == 5) << endl;
cout << (find_closest({ 2,5,6,7,8,8,9 }, 2) == 2) << endl;
cout << (find_closest({ 2,5,6,7,8,8,9 }, 1) == 2) << endl;
cout << (find_closest({ 2,5,6,7,8,8,9 }, 1) == 2) << endl;
cout << (find_closest({ 10 }, 10) == 10) << endl;
cout << (find_closest({ 10 }, 5) == 10) << endl;
cout << (find_closest({ 10 }, 12) == 10) << endl;
cout << (find_closest({ 1,1 }, 1) == 1) << endl;
cout << (find_closest({ 1,1 }, 2) == 1) << endl;
cout << (find_closest({ 1,1 }, 0) == 1) << endl;
cout << (find_closest({ 1,4 }, 3) == 4) << endl;
cout << (find_closest({ 1,4 }, 4) == 4) << endl;
cout << (find_closest({ 1,4 }, 5) == 4) << endl;
cout << (find_closest({ 1,4 }, 2) == 1) << endl;
cout << (find_closest({ 1,4 }, 1) == 1) << endl;
cout << (find_closest({ 1,4 }, -1) == 1) << endl;
}
public class FindClosest {
public static void main (String args[]) {
int array[] = {2,5,6,7,8,8,9};
System.out.println(find(array, 0, array.length-1, 5, -1));
System.out.println(find(array, 0, array.length-1, 11, -1));
System.out.println(find(array, 0, array.length-1, 4, -1));
}
private static int find(int array[], int left, int right, int num, int closestIndex) {
if (left <= right) {
int mid = (left+right)/2;
if (array[mid] == num) return num;
else if (array[mid] < num) {
if (closestIndex == -1) {
closestIndex = mid;
} else {
if (num - array[mid] < Math.abs(num-array[closestIndex])) {
closestIndex = mid;
}
}
return find(array, mid+1, right, num, closestIndex);
} else {
if (closestIndex == -1) {
closestIndex = mid;
} else {
if (array[mid] - num < Math.abs(array[closestIndex] - num)) {
closestIndex = mid;
}
}
return find(array, left, mid-1, num, closestIndex);
}
}
return array[closestIndex];
}
}
In Kotlin
fun nearest( values: IntArray, target: Int): Int {
if ( values.isEmpty() ) throw IllegalArgumentException("No Values")
if ( values.size == 1 ) return values.first()
if ( target > values.last() ) return values.last()
if ( target < values.first() ) return values.first()
val result = values.binarySearch( target )
if ( result > -1 ) return target
val ip = -( result + 1 )
if ( Math.abs( values[ip] - target ) < Math.abs( values[ip-1] - target ) ) return values[ip]
return values [ ip -1 ]
}
fun main(args: Array<String>) {
val values = intArrayOf( 2,5,6,7,8,8,9 )
println( nearest( values, 5 ))
println( nearest( values, 11))
println( nearest( values, 4 ))
println( nearest( values, 3 ))
}
int findClosestNumber(int[] data, int x, int start, int end) {
if(x < data[start]) {
return data[start];
} else if(x > data[end]) {
return data[end];
} else {
if(start < end) {
int mid = (start + end) /2;
if(x > data[mid]) {
return findClosestNumber(data, x, mid+1, end);
} else {
return findClosestNumber(data, x, start, mid);
}
}
return data[start];
}
}
int findClosestNumber(int[] data, int x, int start, int end) {
if(x < data[start]) {
return data[start];
} else if(x > data[end]) {
return data[end];
} else {
if(start < end) {
int mid = (start + end) /2;
if(x > data[mid]) {
return findClosestNumber(data, x, mid+1, end);
} else {
return findClosestNumber(data, x, start, mid);
}
}
return data[start];
}
}
#include<stdio.h>
#include<stdlib.h>
int findvalue(int arr[],int l,int n,int k)
{
if(k < arr[l])
{
return arr[l];
}
else if(k > arr[n-1])
{
return arr[n-1];
}
else
{
if( l< n){
int mid = (l + n) /2;
if(arr[mid]==k)
return arr[mid];
if(k > arr[mid]){
return findvalue(arr,mid+1,n,k);
}
else
{
return findvalue(arr, l, mid, k);
}
}
return arr[l];
}
}
int main()
{
int n,k,i,l=0,rel=0;
scanf("%d",&n);
int arr[n];
for(i=0;i<n;i++)
scanf("%d",&arr[i]);
scanf("%d",&k);
printf("%d",findvalue(arr,l,n,k));
return 0;
}
def find_closest_number(nums_list, target_num):
if nums_list is None: return None
if target_num is None: return None
nums_dict = {i: abs(i-target_num) for i in nums_list}
sorted_dict = sorted(nums_dict.items(), key=lambda x: x[1])
return next(iter(sorted_dict))[0]
n_list=[2,5,6,7,8,8,9]
t_nums = [5, 9, 4, 3]
for num in t_nums:
print(find_closest_number(n_list, num))
function closest(arr, n){
console.log(arr);
if(arr.length === 1) return arr[0];
var left = arr.slice(0, Math.floor(arr.length/2));
var right = arr.slice(Math.floor(arr.length/2), arr.length);
if( Math.abs((n - left[left.length-1])) < Math.abs((n -right[0])) ){
return closest(left, n);
} else {
return closest(right, n);
}
}
function closest(arr, n){
if(arr.length === 1) return arr[0];
var left = arr.slice(0, Math.floor(arr.length/2));
var right = arr.slice(Math.floor(arr.length/2), arr.length);
if( Math.abs((n - left[left.length-1])) < Math.abs((n -right[0])) ){
return closest(left, n);
} else {
return closest(right, n);
}
}
def find_closest(l,low,high,val):
if low == high:
return l[low]
elif high == low+1:
if abs(val - l[high]) < abs(val - l[low]):
return l[high]
else:
return l[low]
mid=(low+high)/2
mid_dif = abs(val - l[mid])
left_dif = abs(val - l[mid-1])
right_dif = abs(val - l[mid+1])
if mid_dif == left_dif == right_dif:
closest_from_left = find_closest(l,low,mid-1,val)
closest_from_right = find_closest(l,mid+1,high,val)
if abs(val - closest_from_left) < abs(val - closest_from_right):
return closest_from_left
else:
return closest_from_right
min_dif = min(mid_dif,left_dif,right_dif)
if mid_dif == min_dif:
return l[mid]
elif left_dif == min_dif:
return find_closest(l,low,mid-1,val)
elif right_dif == min_dif:
return find_closest(l,mid+1,high,val)
l = [2,5,6,7,8,8,8,9]
num_to_find = 13
closest = find_closest(l,0,len(l)-1,num_to_find)
print(closest)
def find_closest(l,low,high,val):
if low == high:
return l[low]
elif high == low+1:
if abs(val - l[high]) < abs(val - l[low]):
return l[high]
else:
return l[low]
mid=(low+high)/2
mid_dif = abs(val - l[mid])
left_dif = abs(val - l[mid-1])
right_dif = abs(val - l[mid+1])
if mid_dif == left_dif == right_dif:
closest_from_left = find_closest(l,low,mid-1,val)
closest_from_right = find_closest(l,mid+1,high,val)
if abs(val - closest_from_left) < abs(val - closest_from_right):
return closest_from_left
else:
return closest_from_right
min_dif = min(mid_dif,left_dif,right_dif)
if mid_dif == min_dif:
return l[mid]
elif left_dif == min_dif:
return find_closest(l,low,mid-1,val)
elif right_dif == min_dif:
return find_closest(l,mid+1,high,val)
l = [2,5,6,7,8,8,8,9]
num_to_find = 13
closest = find_closest(l,0,len(l)-1,num_to_find)
print(closest)
public class Solution {
public int getClosetVal(int[] arr, int target, int start, int end, int prev) {
if (end == start + 1) {
// one element
if (Math.abs(target-prev) < Math.abs(target-arr[start])) {
return prev;
}
return arr[start];
}
int midpt = (start + end) / 2;
if (arr[midpt] == target) {
return arr[midpt];
} else if (arr[midpt] > target) {
// search left
return getClosetVal(arr, target, start, midpt, arr[midpt]);
} else {
// search right
return getClosestVal(arr, target, midpt+1, end, arr[midpt]);
}
}
public static void main(String[] args) {
Solution s = new Solution();
int[] arr = new int[] {1,4,7,7};
s.getClosestVal(arr, 2, 0, arr.length, arr[0]);
}
}
public class Solution {
/**
* Works like normal binary search, except we keep track of a previous value.
* When we are certain there is no match found, we return whichever is closer to target:
* (a) current element or (b) previous element.
**/
public int getClosestVal(int[] arr, int target, int start, int end, int prev) {
if (end == start + 1) {
// one element
if (Math.abs(target-prev) < Math.abs(target-arr[start])) {
return prev;
}
return arr[start];
}
int midpt = (start + end) / 2;
if (arr[midpt] == target) {
return arr[midpt];
} else if (arr[midpt] > target) {
// search left
return getClosestVal(arr, target, start, midpt, arr[midpt]);
} else {
// search right
return getClosestVal(arr, target, midpt+1, end, arr[midpt]);
}
}
public static void main(String[] args) {
Solution s = new Solution();
int[] arr = new int[] {1,4,7,7};
int target = 2;
s.getClosestVal(arr, target, 0, arr.length, arr[0]);
}
}
public static void abc(final int n) {
Integer a[] = {2, 5, 6, 7, 8, 8, 9};
Integer min = null;
Integer index = null;
for (int i = 0; i < a.length; i++) {
int x = Math.abs(a[i] - n);
if (x == 0) {
index = a[i];
break;
}
if (min == null) {
min = x;
index = a[i];
}
if (min > x) {
min = x;
index = a[i];
}
}
System.out.println(index);
compareValue = (a=Infinity, b=Infinity, c=Infinity, key) =>{
if((Math.abs(a-key) < Math.abs(b-key)) && (Math.abs(a-key) < Math.abs(c-key))){
return a;
}
if((Math.abs(b-key) <= Math.abs(c-key)) && (Math.abs(b-key) <= Math.abs(a-key))){
return b;
}
return c
}
binarySearch = (array, key) => {
var start = 0;
var end = array.length - 1;
var mid = 0;
while(start <= end){
mid = Math.ceil((start + end)/2);
if(key == array[mid]){
return key;
}
if(key < array[mid]){
end = mid - 1;
}else{
start = mid + 1;
}
}
return compareValue(array[mid-1], array[mid], array[mid+1], key);
}
var array = [2,5,6,7,8,8,9];
console.log(binarySearch(array, 4));
In Python, I would suggest:
def ClosestValue(array,number):
array.sort()
el = array[0]
i=0
while (el < number and i < len(array)-1):
i+=1
el = array[i]
if i <= len(array)-1:
dist1 = (array[i] - number)**2
if dist1==0:
return array[i]
elif i>0:
dist2= (array[i-1] - number)**2
if dist2 < dist1:
return array[i-1]
else:
return array[i]
else:
return array[i-1]
def nearest_value(a,key)
low = 0
high= a.length - 1
while low < high
mid = (low + high)/2
dml = (a[mid-1] - key ).abs
dmh = (a[mid+1] - key) .abs
dm = (a[mid] - key ).abs
return a[mid] if dm == 0 || (dmh > dm && dml > dm)
return a[mid+1] if dmh == 0
return a[mid-1] if dml == 0
if dm > dml
high = mid -1
else
low = mid +1
end
end
return a[low]
end
#!/usr/bin/python
def closest_value(arr_list, target):
diff = 0
prev = 0
next_diff = 0
j = 1
i = 0
index = 0
while i < len(arr_list) - 1 and i < j:
j = i + 1
if target == arr_list[i]:
return target
if j < len(arr_list):
diff = abs(abs(arr_list[i]) - abs(target))
next_diff = abs(abs(arr_list[j]) - abs(target))
if next_diff < diff:
prev = next_diff
index = j
i += 1
j += 1
return abs(arr_list[index])
def main():
arr_li = [-2,-5,6,7,8,8,-9]
#number = int(raw_input("Accept how many numbers?"))
target = int(raw_input("enter the target number"))
'''for i in range(number):
arr_li.append(int(raw_input("enter values")))'''
print "Closest number from array is {0}".format(closest_value(arr_li, target))
if __name__ == '__main__':
main()
package com.career_cup;
/**
* Given an array of sorted integers and find the closest value to the given number. Array may contain duplicate values and negative numbers.
* <p>
* Example : Array : 2,5,6,7,8,8,9
* Target number : 5
* Output : 5
* <p>
* Target number : 11
* Output : 9
* <p>
* Target Number : 4
* Output : 5
*/
public class ClosestValueInAnArray {
public static void main(String[] args) {
System.out.println("Closest Element to the target "+5+" is ::" + findClosestValueToTheTargetValue(new int[]{2, 5, 6, 7, 8, 8, 9}, 5));
System.out.println("Closest Element to the target "+4+" is ::" + findClosestValueToTheTargetValue(new int[]{2, 5, 6, 7, 8, 8, 9}, 4));
}
public static int findClosestValueToTheTargetValue(int[] arr, int target) {
int closestDifference = Integer.MAX_VALUE;
int closestElement = 0;
for (int i : arr) {
if (Math.abs(target - i) < closestDifference) {
closestDifference = Math.abs(target - i);
closestElement = i;
}
}
return closestElement;
}
}
function findNearest(target, array) {
var match;
for(var index = 1; index < (input.length - 1); index += 1) {
var array = input;
var elem = array[index];
if(target == elem) {
match = elem;
break;
} else if(target > elem && elem != array[index+1]) {
if(target - elem < (array[index + 1] - target)) {
match = elem;
break;
} else if(target < array[index + 1]){
match = array[index + 1];
break;
}
}
}
if(!match) {
if(target < input[1]) {
match = input[0];
} else {
match = input[input.length - 1];
}
}
return match;
}
findNearest(8);
private static int findClosestValue(int[] num, int target){
if(num.length == 1){
return num[num.length-1];
}
for(int i = 0; i < num.length ; i++){
if(num[i] == target){
return num[i];
}
if(num[i] > target){
return num[i];
}else if(i != num.length-1 && (num[i] < target && num[i+1] > target)){
return num[i+1];
}
}
return num[num.length-1];
}
#include <iostream>
using namespace std;
int main() {
int n,min=32767,diff,var;
cin>>n;
int a[n];
int target;
cin>>target;
for(int i=0;i<n;i++)
{
cin>>a[i];
if(a[i]<=target)
{
diff=target-a[i];
}
if(a[i]>target)
{
diff=a[i]-target;
}
if(min>diff)
{
min=diff;
var=a[i];
}
}
cout<<var;
return 0;
}
#include <iostream>
using namespace std;
int main() {
int n,min=32767,diff,var;
cin>>n;
int a[n];
int target;
cin>>target;
for(int i=0;i<n;i++)
{
cin>>a[i];
if(a[i]<=target)
{
diff=target-a[i];
}
if(a[i]>target)
{
diff=a[i]-target;
}
if(min>diff)
{
min=diff;
var=a[i];
}
}
cout<<var;
return 0;
}
#include <iostream>
using namespace std;
int main()
{
int a[10],i,x,n,val;
cin>>n>>x;
for(i=0;i<n;i++)
cin>>a[i];
int min=x-a[0];
for(i=0;i<n;i++)
{
if(a[i]<x)
{
if((x-a[i])<=min)
{
min=x-a[i];
val=a[i];
}
// min=a[i];
}
else{
if((a[i]-x)<=min)
{
min=a[i]-x;
val=a[i];
}
//min=a[i];
}
}
cout<<val;
return 0;
}
#include <iostream>
using namespace std;
int main()
{
int a[10],i,x,n,val;
cin>>n>>x;
for(i=0;i<n;i++)
cin>>a[i];
int min=x-a[0];
for(i=0;i<n;i++)
{
if(a[i]<x)
{
if((x-a[i])<=min)
{
min=x-a[i];
val=a[i];
}
// min=a[i];
}
else{
if((a[i]-x)<=min)
{
min=a[i]-x;
val=a[i];
}
//min=a[i];
}
}
cout<<val;
return 0;
}
Language Java
private static int findCloseNumber(int[] input, int targetNumber) {
int minimumDistance = Integer.MAX_VALUE;
int nearNumber = 0;
for (int i = 0; i < input.length; i++) {
if (input[i] == targetNumber) {
nearNumber=input[i];
break;
}else{
int tmpMinimumDistance = Math.abs(targetNumber - input[i]);
if (tmpMinimumDistance < minimumDistance) {
minimumDistance = tmpMinimumDistance;
nearNumber=input[i];
}
}
}
return nearNumber;
}
Language - Java
private static int findCloseNumber(int[] input, int targetNumber) {
int minimumDistance = Integer.MAX_VALUE;
int nearNumber = 0;
for (int i = 0; i < input.length; i++) {
if (input[i] == targetNumber) {
nearNumber=input[i];
break;
}else{
int tmpMinimumDistance = Math.abs(targetNumber - input[i]);
if (tmpMinimumDistance < minimumDistance) {
minimumDistance = tmpMinimumDistance;
nearNumber=input[i];
}
}
}
return nearNumber;
}
#include <stdio.h>
#include<stdlib.h>
int main()
{
int a[20],n,num,k,i,h,c;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
printf("enter the element for which you want to search closest");
scanf("%d",&num);
k=abs(num-a[0]);
h=a[0];
for(i=1;i<n;i++)
{
c=abs(num-a[i]);
if(c<k)
{
k=c;
h=a[i];
}
}
printf("%d",h);
return 0;
}
#include <stdio.h>
#include<stdlib.h>
int main()
{
int a[20],n,num,k,i,h,c;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
printf("enter the element for which you want to search closest");
scanf("%d",&num);
k=abs(num-a[0]);
h=a[0];
for(i=1;i<n;i++)
{
c=abs(num-a[i]);
if(c<k)
{
k=c;
h=a[i];
}
}
printf("%d",h);
return 0;
}
#include <stdio.h>
#include<stdlib.h>
int main()
{
int a[20],n,num,k,i,h,c;
printf("Enter the size of array:")
scanf("%d",&n);
printf("Enter the array elements:")
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
printf("enter the element for which you want to search closest:");
scanf("%d",&num);
k=abs(num-a[0]);
h=a[0];
for(i=1;i<n;i++)
{
c=abs(num-a[i]);
if(c<k)
{
k=c;
h=a[i];
}
}
printf("The closest num is %d",h);
return 0;
}
#include <stdio.h>
#include<stdlib.h>
int main()
{
int a[20],n,num,k,i,h,c;
printf("Enter the size of array:")
scanf("%d",&n);
printf("Enter the array elements:")
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
printf("enter the element for which you want to search closest:");
scanf("%d",&num);
k=abs(num-a[0]);
h=a[0];
for(i=1;i<n;i++)
{
c=abs(num-a[i]);
if(c<k)
{
k=c;
h=a[i];
}
}
printf("The closest num is %d",h);
return 0;
}
#include <stdio.h>
#include<stdlib.h>
int main()
{
int a[20],n,num,k,i,h,c;
printf("Enter the size of array:")
scanf("%d",&n);
printf("Enter the array elements:")
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
printf("enter the element for which you want to search closest:");
scanf("%d",&num);
k=abs(num-a[0]);
h=a[0];
for(i=1;i<n;i++)
{
c=abs(num-a[i]);
if(c<k)
{
k=c;
h=a[i];
}
}
printf("The closest num is %d",h);
return 0;
}
java version
public class FindClosest{
public static void main(String[] args){
int[] array = new int[]{2,5,5,8,9};
int target = 6;
System.out.println(new FindClosest().closest(array,target,0,array.length-1));
}
private int closest(int[] a, int t, int b, int e ){
if(b==e){
return a[b];
}
if(e-b==1){
return a[e]-t<t-a[b]?a[e]:a[b];
}
int m = (b+e)/2;
if(t==a[m]){
return a[m];
}
if(t<a[m]){
return closest(a, t, b, m );
}else{
return closest(a, t, m, e );
}
}
}
{{
int find(int[] arr, int start, int end, int num)
{
var mid = start + (end - start) / 2;
var value = arr[mid];
if (value == num)
{
return num;
}
if (start == end)
{
var l = start < 1 ? arr[0] : arr[start - 1];
var r = start + 1 >= arr.Length ? arr[start] : arr[start + 1];
var m = value;
var dif1 = Math.Abs(num - l);
var dif2 = Math.Abs(num - m);
var dif3 = Math.Abs(num - r);
if (dif1 < dif2)
return l;
if (dif2 < dif3)
return m;
return r;
}
if (value >= num)
{
return find(arr, start, mid - 1, num);
}
else
{
return find(arr, mid + 1, end, num);
}
}
int findClosest(int[] arr, int num)
{
return find(arr, 0, arr.Length - 1, num);
}
}}
public static void main(String[] args){
int[] arr = {1, 4};
int n = -1;
int r = closest(arr, n);
System.out.println(r);
}
//2,5,6,7,8,8,9
public static int closest(int[] arr, int n){
int min = Integer.MAX_VALUE;
int minv = 0;
int l = 0;
int h = arr.length-1;
while(l <= h){
int mid = (h-l)/2+l;
int diff = Math.abs(n-arr[mid]);
if(diff == 0)
return arr[mid];
if(diff < min){
min = diff;
minv = arr[mid];
}
if(arr[mid] > n)
h = mid-1;
else
l = mid+1;
}
return minv;
}
I would use
std::lower_bound
and
std::upper_bound
#include <stdio.h>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cmath>
void search_closest_number(const std::vector<int>& numbers, int search_number)
{
if(numbers.empty()) {
return;
}
std::vector<int>::const_iterator lower_iter = std::lower_bound(numbers.begin(), numbers.end(), search_number);
std::vector<int>::const_iterator upper_iter = std::upper_bound(numbers.begin(), numbers.end(), search_number);
if(upper_iter != numbers.end() && lower_iter != numbers.end()) {
int diffUpper = abs(search_number - (*upper_iter));
if(lower_iter != numbers.begin()) {
lower_iter--;
}
int diffLower = abs(search_number - (*lower_iter));
std::cout << ((diffUpper < diffLower) ? (*upper_iter) : (*lower_iter)) << std::endl;
} else if(upper_iter == numbers.end() && lower_iter != numbers.end()) {
std::cout << *lower_iter << std::endl;
} else if(lower_iter == numbers.end() && upper_iter != numbers.end()) {
std::cout << *upper_iter << std::endl;
} else {
std::cout << numbers.back() << std::endl;
}
}
int main(int argc, char** argv)
{
std::vector<int> numbers = { 4, 5, 5, 8, 8, 9 };
search_closest_number(numbers, 4); // 4
search_closest_number(numbers, 5); // 5
search_closest_number(numbers, 11); // 9
search_closest_number(numbers, 6); // 5
search_closest_number(numbers, 1); // 4
return 0;
}
- Vijay November 17, 2017