Ищем алгоритм поиска в обоих направлениях — c / c ++ / awk

Question

Ищем алгоритм поиска в обоих направлениях — c / c ++ / awk

Я работаю над некоторым вычислительным моделированием, в котором мне нужно искать данные, которые расположены нерегулярно и данные не сортируются, поэтому вот сценарий

Мои образцы данных точек

Итак, алгоритм поиска, который я ищу, выглядит так,

скажи если key = 2 тогда функция должна вернуть индекс 2 так как он доступен, скажем, например, я хочу искать 3его нет в col1, поскольку он недоступен, мне нужно искать ближайшее значение в обоих направлениях, которое является индексом 2 а также 5

в случае awk Точный ключ можно искать, используя что-то вроде этого

  function search(Arr,key){
if((key in Arr))
return key
}

Но я действительно не знаю, но искать ближайшее значение в верхнем и нижнем направлении, в случае, если точный ключ не найден

Я надеюсь, что мое требование ясно, в случае отрицательного голосования, пожалуйста, оставьте свой комментарий, так как моя проблема из-за меньшей репутации (новичок в этом форуме), я не могу проголосовать за полезные ответы, пожалуйста, сотрудничайте.

0

awk c++shell

Решение

Другие решения

Shell решение,

perl -lane'
BEGIN{ $k=pop }
push @r, [@F];
END {
for (sort{ $a->[0] <=> $b->[0] } @r) {
$v= $_->[0] <=> $k;
$h{$v} = $_->[1];
last if $v >0;
}
print join " ", ($h{0} or @h{-1,1});
}
' file 3

выход

14 10

3

В Gnu Awk версии 4 вы можете использовать PROCINFO["sorted_in"] лайк:

gawk -vkey=7 -f a.awk file

где a.awk является:

{
a[$1]=$2
}
END {
if (key in a)
print "Found key "key" with value "a[key]
else {
PROCINFO["sorted_in"]="@ind_num_asc"for (i in a) {
if (i+0>key) { k=i; break}
j=i
}
if (j)
print "Prev key: "j
if(k)
print "Next key: "k
}
}

Выход:

$gawk -vkey=6 -f a.awk file

Prev key: 5
Next key: 7

$gawk -vkey=5 -f a.awk file

Found key 5 with value 10

2

Источник

Accepted Answer

Поскольку вы не отсортированы, лучше всего искать точный, нижний и верхний одновременно, чтобы перебирать данные только один раз.

#include <iostream>
#include <vector>
#include <utility>

using Samples = std::vector<std::pair<int,int>>;

Samples::const_iterator Find( Samples const & samp_, int val_, Samples::const_iterator & prev_, Samples::const_iterator & next_ ) {
auto end = std::end(samp_);
auto lower = end;
auto upper = end;
auto it = begin(samp_);
for( ; it!=end; ++it) {
if ( it->first == val_ )
return it;
if ( it->first < val_ && ( lower == end || lower->first < it->first ) )
lower = it;
else if ( it->first > val_ && ( upper == end || upper->first > it->first ) )
upper = it;
}
prev_ = lower;
next_ = upper;
return end;
}

std::ostream & operator<<( std::ostream & os, std::pair<int,int> const & p ) {
return os << "( " << p.first << ", " << p.second << " )";
}

int main() {
Samples samps { {1,92}, {9,45},{7,22},{2,14},{5,10} };

auto test = [&] ( int v ) {
Samples::const_iterator lower;
Samples::const_iterator upper;
auto result = Find( samps, v, lower, upper );
if ( result != end( samps ) ) {
std::cout << "found " << *result << std::endl;
} else {
std::cout << "not found ";
if ( lower  != end( samps ) )
std::cout << "lower is " << *lower;
else
std::cout << "no lower";
if ( upper  != end( samps ) )
std::cout << " upper is " << *upper;
else
std::cout << " no upper";
std::cout << std::endl;
}
};
test(2);
test(3);
test(12);
test(-1);
}

И результат:

found ( 2, 14 )
not found lower is ( 2, 14 ) upper is ( 5, 10 )
not found lower is ( 9, 45 ) no upper
not found no lower upper is ( 1, 92 )

2