在python3中实现查找数组中最接近与某值的元素操作

我就废话不多说了，直接上代码吧！

import datetime

def find_close(arr, e):
start_time = datetime.datetime.now()

size = len(arr)
idx = 0
val = abs(e - arr[idx])

for i in range(1, size):
 val1 = abs(e - arr[i])
 if val1 < val:
  idx = i
  val = val1

use_time = datetime.datetime.now() - start_time

return arr[idx], use_time.seconds * 1000 + use_time.microseconds / 1000

def find_close_fast(arr, e):
start_time = datetime.datetime.now()

low = 0
high = len(arr) - 1
idx = -1

while low <= high:
 mid = int((low + high) / 2)
 if e == arr[mid] or mid == low:
  idx = mid
  break
 elif e > arr[mid]:
  low = mid
 elif e < arr[mid]:
  high = mid

if idx + 1 < len(arr) and abs(e - arr[idx]) > abs(e - arr[idx + 1]):
 idx += 1

use_time = datetime.datetime.now() - start_time

return arr[idx], use_time.seconds * 1000 + use_time.microseconds / 1000

if __name__ == "__main__":
arr = []

f = open("1Mints.txt")
for line in f:
 arr.append(int(line))
f.close()

arr.sort()

while 1:
 e = int(input("input a number:"))
 print("find_close ", find_close(arr, e))
 print ("find_close_fast ", find_close_fast(arr, e))

补充拓展：查询集合中最接近某个数的数

查询集合中最接近某个数的数

/*
★实验任务
给你一个集合，一开始是个空集，有如下两种操作：

向集合中插入一个元素。
询问集合中最接近某个数的数是多少。
★数据输入
输入第一行为一个正整数 N，表示共有 N 个操作。
接下来 N 行，每行一个操作。
对于第一个操作，输入格式为 1 x，表示往集合里插入一个值为 x 的元素。
对于第二个操作，输入格式为 2 x，表示询问集合中最接近 x 的元素是什么。
1<=N<=100000,1<=x<=1000000000。

★数据输出
对于所有的第二个操作，输出一个或者两个整数，表示最接近 x 的元素，有
两个数的情况，按照升序输出，并用一个空格隔开。
如果集合为空，输出一行“Empty!”
数据保证插入的元素两两不同。

输入示例 输出示例

5 Empty!
2 1 2
1 2 2 4
2 3
1 4
2 3
*/

解题思路

一、采用C++ 中map容器,因为它可以实时对输入的元素进行排序。（map的使用可自行百度）

二、当集合为空时，输出“Empty!”；当集合中只有一个元素时，直接输出该元素。

三、下面重点看一般的情况。

1.先查找集合中是否有查询的元素，有则输出该元素

2.没有的话，将该元素先插入集合中，再查找该元素处于集合的某个位置。

若该元素在集合的首位，则输出该数的下一位。

若该元素在集合的末位，则输出该数的上一位。

否则，判断它左右元素的值与它的差的绝对值，输出差的绝对值较小的那个元素。若相等，则同时输出。

#include <iostream>
#include <map>
#include <cmath>
using namespace std;
map <long long ,int> a;
int main()
{
a.clear() ;
int N,t;
long long int x;
cin >> N;
while(N--)
{
cin >> t >> x;
if(t==1)
a[x]=1;
else
{
if(a.empty() )//判断集合是否为空
cout << "Empty!\n" ;
else
{
if(a.size() == 1 )//若只有一个元素，则直接输出
cout << a.begin()->first << endl;
else
{
map <long long ,int>::iterator it,m,n;
it=a.find(x);
if(it!=a.end() )
{
cout << x <<endl;
continue;
}
a[x]=1;
it=a.find(x);
if(it == a.begin() )
{
it++;
cout << it -> first << endl;
}
else if(it == a.end() )
{
it--;
cout << it -> first << endl;
}
else
{
m=--it;//m和n分别指向it的左右两侧
it++;
n=++it;
if(abs(m -> first - x) > abs(n -> first - x))
cout << n -> first << endl;
else if(abs(m -> first - x) == abs(n -> first - x))
cout << m -> first << " " << n -> first << endl;
else
cout << m -> first << endl;
}
a.erase(a.find(x) );
}
}
}
}
return 0;
}

来源：https://blog.csdn.net/GIS_BT/article/details/92004228