OnR*_*der 2 search approximate
考虑一个整数数组(假设是排序的); 我想以最快的方式找到最接近给定整数的整数的数组索引.并且在存在多种可能性的情况下,算法应该识别所有.
示例:考虑T =(3,5,24,65,67,87,129,147,166),如果给定的整数为144,则代码应将147标识为最接近的整数,并给出数组索引7对应于该条目.对于66的情况,算法应识别65和67.
是否有O(1)或至少O(log N)算法来执行此操作？直接搜索算法(二进制搜索,树搜索,散列等)实现将不起作用,因为那些将需要完美匹配.有没有办法可以修改这些来处理近似搜索？
我正在开发一个C代码.
谢谢