Mamy listę jednokierunkową zawierającą liczby, zadaniem jest znalezienie liczby najbliższej do liczby zadanej.
Np podaje 10, i znajduje liczbę liście która jest najbliższa np 9.
Jak napisać to w c++?
0
0
Iterujesz po kolei i zapisujesz w jakiejś zmiennej wartość najbliższej liczby (albo jeszcze lepiej iterator do niej). Jeśli jest równa, to przerywasz wyszukiwanie. Jeśli lista jest posortowana to szukasz punkty w którym przeskoczysz szukaną liczbę i po nim przerywasz. Szybciej niż iterować po kolei się nie da.
0
Wydajniej było by stworzyć dodatkową zmienną na "aktualnie najmniejszą" różnicę.
0
A ile takich testów chcesz przeprowadzać dla tych samych danych? Bo posortowanie danych i szukanie połówkowe, albo wrzucenie tego do drzewa da ci
O(nlogn) + Xlog(n)
a szukanie liniowe da ci
XO(n)
więc sporo zależy tutaj od tego ile razy szukasz.