Problem
* Given - a number (n) and a sorted array
* Find a number in the array having least difference with the given number (n).
* */
Solution
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Find a number in the array having least difference with the given number (n)
Created Date : 08-07-2013
Last Modified :
============================================================================
*/
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <numeric>
using namespace std;
int FindNearestNum(int* arr, int len, int n)
{
if(len == 1) return arr[0];
if(n < arr[0]) return arr[0];
if(n > arr[len - 1]) return arr[len - 1];
int low = 0;
int up = len - 1;
while(low <= up){
int mid = low + (up - low) / 2;
if(arr[mid] == n){
return n;
}
else if(arr[mid] > n){
up = mid - 1;
}
else{
low = mid + 1;
}
}
return abs(arr[low] - n) > abs(arr[up] - n) ? arr[up] : arr[low];
}
void DoTest(int* arr, int len, int n)
{
cout << "The array is: " << endl;
for(int i = 0; i < len; ++i){
cout << setw(3) << arr[i];
}
cout << endl;
cout << "The number to find is: " << n << endl;
int foundNum = FindNearestNum(arr, len, n);
cout << "The nearest num is: " << foundNum << endl;
auto expectedNum = min_element(arr, arr + len, [=](int i, int j) -> bool{
return abs(n - i) < abs(n - j);
});
cout << "The expected num is: " << *expectedNum << endl;
cout << "---------------------------------------" << endl;
}
int main(int argc, char* argv[])
{
int arr[] = { -1, 0, 2, 3, 4, 8, 9, 20, 29, 43, 44, 45, 46, 47, 48, 49 };
for (int i = -3; i < 50; i ++){
DoTest(arr, sizeof(arr)/sizeof(arr[0]), i);
}
int arr1[] = { -2 };
for (int i = -3; i < 5; i += 3){
DoTest(arr1, sizeof(arr1)/sizeof(arr1[0]), i);
}
int arr2[] = { -2, 7 };
for (int i = -3; i < 5; i += 3){
DoTest(arr2, sizeof(arr2)/sizeof(int), i);
}
int arr3[] = { -2, 7, 100 };
for (int i = -3; i < 5; i += 3) {
DoTest(arr3, sizeof(arr3)/sizeof(int), i);
}
return 0;
}
Output
The array is:
-1 0 2 3 4 8 9 20 29 43 44 45 46 47 48 49
The number to find is: -3
The nearest num is: -1
The expected num is: -1
---------------------------------------
The array is:
-1 0 2 3 4 8 9 20 29 43 44 45 46 47 48 49
The number to find is: -2
The nearest num is: -1
The expected num is: -1
---------------------------------------
The array is:
-1 0 2 3 4 8 9 20 29 43 44 45 46 47 48 49
The number to find is: -1
The nearest num is: -1
The expected num is: -1
---------------------------------------
The array is:
-1 0 2 3 4 8 9 20 29 43 44 45 46 47 48 49
The number to find is: 0
The nearest num is: 0
The expected num is: 0
---------------------------------------
The array is:
-1 0 2 3 4 8 9 20 29 43 44 45 46 47 48 49
The number to find is: 1
The nearest num is: 2
The expected num is: 0
---------------------------------------
The array is:
-1 0 2 3 4 8 9 20 29 43 44 45 46 47 48 49
The number to find is: 2
The nearest num is: 2
The expected num is: 2
---------------------------------------
The array is:
-1 0 2 3 4 8 9 20 29 43 44 45 46 47 48 49
The number to find is: 3
The nearest num is: 3
The expected num is: 3
---------------------------------------
The array is:
-1 0 2 3 4 8 9 20 29 43 44 45 46 47 48 49
The number to find is: 4
The nearest num is: 4
The expected num is: 4
---------------------------------------
The array is:
-1 0 2 3 4 8 9 20 29 43 44 45 46 47 48 49
The number to find is: 5
The nearest num is: 4
The expected num is: 4
---------------------------------------
The array is:
-1 0 2 3 4 8 9 20 29 43 44 45 46 47 48 49
The number to find is: 6
The nearest num is: 8
The expected num is: 4
---------------------------------------
The array is:
-1 0 2 3 4 8 9 20 29 43 44 45 46 47 48 49
The number to find is: 7
The nearest num is: 8
The expected num is: 8
---------------------------------------
The array is:
-1 0 2 3 4 8 9 20 29 43 44 45 46 47 48 49
The number to find is: 8
The nearest num is: 8
The expected num is: 8
---------------------------------------
The array is:
-1 0 2 3 4 8 9 20 29 43 44 45 46 47 48 49
The number to find is: 9
The nearest num is: 9
The expected num is: 9
---------------------------------------
The array is:
-1 0 2 3 4 8 9 20 29 43 44 45 46 47 48 49
The number to find is: 10
The nearest num is: 9
The expected num is: 9
---------------------------------------
The array is:
-1 0 2 3 4 8 9 20 29 43 44 45 46 47 48 49
The number to find is: 11
The nearest num is: 9
The expected num is: 9
---------------------------------------
The array is:
-1 0 2 3 4 8 9 20 29 43 44 45 46 47 48 49
The number to find is: 12
The nearest num is: 9
The expected num is: 9
---------------------------------------
The array is:
-1 0 2 3 4 8 9 20 29 43 44 45 46 47 48 49
The number to find is: 13
The nearest num is: 9
The expected num is: 9
---------------------------------------
The array is:
-1 0 2 3 4 8 9 20 29 43 44 45 46 47 48 49
The number to find is: 14
The nearest num is: 9
The expected num is: 9
---------------------------------------
The array is:
-1 0 2 3 4 8 9 20 29 43 44 45 46 47 48 49
The number to find is: 15
The nearest num is: 20
The expected num is: 20
---------------------------------------
The array is:
-1 0 2 3 4 8 9 20 29 43 44 45 46 47 48 49
The number to find is: 16
The nearest num is: 20
The expected num is: 20
---------------------------------------
The array is:
-1 0 2 3 4 8 9 20 29 43 44 45 46 47 48 49
The number to find is: 17
The nearest num is: 20
The expected num is: 20
---------------------------------------
The array is:
-1 0 2 3 4 8 9 20 29 43 44 45 46 47 48 49
The number to find is: 18
The nearest num is: 20
The expected num is: 20
---------------------------------------
The array is:
-1 0 2 3 4 8 9 20 29 43 44 45 46 47 48 49
The number to find is: 19
The nearest num is: 20
The expected num is: 20
---------------------------------------
The array is:
-1 0 2 3 4 8 9 20 29 43 44 45 46 47 48 49
The number to find is: 20
The nearest num is: 20
The expected num is: 20
---------------------------------------
The array is:
-1 0 2 3 4 8 9 20 29 43 44 45 46 47 48 49
The number to find is: 21
The nearest num is: 20
The expected num is: 20
---------------------------------------
The array is:
-1 0 2 3 4 8 9 20 29 43 44 45 46 47 48 49
The number to find is: 22
The nearest num is: 20
The expected num is: 20
---------------------------------------
The array is:
-1 0 2 3 4 8 9 20 29 43 44 45 46 47 48 49
The number to find is: 23
The nearest num is: 20
The expected num is: 20
---------------------------------------
The array is:
-1 0 2 3 4 8 9 20 29 43 44 45 46 47 48 49
The number to find is: 24
The nearest num is: 20
The expected num is: 20
---------------------------------------
The array is:
-1 0 2 3 4 8 9 20 29 43 44 45 46 47 48 49
The number to find is: 25
The nearest num is: 29
The expected num is: 29
---------------------------------------
The array is:
-1 0 2 3 4 8 9 20 29 43 44 45 46 47 48 49
The number to find is: 26
The nearest num is: 29
The expected num is: 29
---------------------------------------
The array is:
-1 0 2 3 4 8 9 20 29 43 44 45 46 47 48 49
The number to find is: 27
The nearest num is: 29
The expected num is: 29
---------------------------------------
The array is:
-1 0 2 3 4 8 9 20 29 43 44 45 46 47 48 49
The number to find is: 28
The nearest num is: 29
The expected num is: 29
---------------------------------------
The array is:
-1 0 2 3 4 8 9 20 29 43 44 45 46 47 48 49
The number to find is: 29
The nearest num is: 29
The expected num is: 29
---------------------------------------
The array is:
-1 0 2 3 4 8 9 20 29 43 44 45 46 47 48 49
The number to find is: 30
The nearest num is: 29
The expected num is: 29
---------------------------------------
The array is:
-1 0 2 3 4 8 9 20 29 43 44 45 46 47 48 49
The number to find is: 31
The nearest num is: 29
The expected num is: 29
---------------------------------------
The array is:
-1 0 2 3 4 8 9 20 29 43 44 45 46 47 48 49
The number to find is: 32
The nearest num is: 29
The expected num is: 29
---------------------------------------
The array is:
-1 0 2 3 4 8 9 20 29 43 44 45 46 47 48 49
The number to find is: 33
The nearest num is: 29
The expected num is: 29
---------------------------------------
The array is:
-1 0 2 3 4 8 9 20 29 43 44 45 46 47 48 49
The number to find is: 34
The nearest num is: 29
The expected num is: 29
---------------------------------------
The array is:
-1 0 2 3 4 8 9 20 29 43 44 45 46 47 48 49
The number to find is: 35
The nearest num is: 29
The expected num is: 29
---------------------------------------
The array is:
-1 0 2 3 4 8 9 20 29 43 44 45 46 47 48 49
The number to find is: 36
The nearest num is: 43
The expected num is: 29
---------------------------------------
The array is:
-1 0 2 3 4 8 9 20 29 43 44 45 46 47 48 49
The number to find is: 37
The nearest num is: 43
The expected num is: 43
---------------------------------------
The array is:
-1 0 2 3 4 8 9 20 29 43 44 45 46 47 48 49
The number to find is: 38
The nearest num is: 43
The expected num is: 43
---------------------------------------
The array is:
-1 0 2 3 4 8 9 20 29 43 44 45 46 47 48 49
The number to find is: 39
The nearest num is: 43
The expected num is: 43
---------------------------------------
The array is:
-1 0 2 3 4 8 9 20 29 43 44 45 46 47 48 49
The number to find is: 40
The nearest num is: 43
The expected num is: 43
---------------------------------------
The array is:
-1 0 2 3 4 8 9 20 29 43 44 45 46 47 48 49
The number to find is: 41
The nearest num is: 43
The expected num is: 43
---------------------------------------
The array is:
-1 0 2 3 4 8 9 20 29 43 44 45 46 47 48 49
The number to find is: 42
The nearest num is: 43
The expected num is: 43
---------------------------------------
The array is:
-1 0 2 3 4 8 9 20 29 43 44 45 46 47 48 49
The number to find is: 43
The nearest num is: 43
The expected num is: 43
---------------------------------------
The array is:
-1 0 2 3 4 8 9 20 29 43 44 45 46 47 48 49
The number to find is: 44
The nearest num is: 44
The expected num is: 44
---------------------------------------
The array is:
-1 0 2 3 4 8 9 20 29 43 44 45 46 47 48 49
The number to find is: 45
The nearest num is: 45
The expected num is: 45
---------------------------------------
The array is:
-1 0 2 3 4 8 9 20 29 43 44 45 46 47 48 49
The number to find is: 46
The nearest num is: 46
The expected num is: 46
---------------------------------------
The array is:
-1 0 2 3 4 8 9 20 29 43 44 45 46 47 48 49
The number to find is: 47
The nearest num is: 47
The expected num is: 47
---------------------------------------
The array is:
-1 0 2 3 4 8 9 20 29 43 44 45 46 47 48 49
The number to find is: 48
The nearest num is: 48
The expected num is: 48
---------------------------------------
The array is:
-1 0 2 3 4 8 9 20 29 43 44 45 46 47 48 49
The number to find is: 49
The nearest num is: 49
The expected num is: 49
---------------------------------------
The array is:
-2
The number to find is: -3
The nearest num is: -2
The expected num is: -2
---------------------------------------
The array is:
-2
The number to find is: 0
The nearest num is: -2
The expected num is: -2
---------------------------------------
The array is:
-2
The number to find is: 3
The nearest num is: -2
The expected num is: -2
---------------------------------------
The array is:
-2 7
The number to find is: -3
The nearest num is: -2
The expected num is: -2
---------------------------------------
The array is:
-2 7
The number to find is: 0
The nearest num is: -2
The expected num is: -2
---------------------------------------
The array is:
-2 7
The number to find is: 3
The nearest num is: 7
The expected num is: 7
---------------------------------------
The array is:
-2 7100
The number to find is: -3
The nearest num is: -2
The expected num is: -2
---------------------------------------
The array is:
-2 7100
The number to find is: 0
The nearest num is: -2
The expected num is: -2
---------------------------------------
The array is:
-2 7100
The number to find is: 3
The nearest num is: 7
The expected num is: 7
---------------------------------------
Press any key to continue . . .