Собственно, сабж. Надо к понедельнику сделать на Яве, а я туплю нипадецки. Вот что написал:
| Код |
public static void sort (List a) {
if(a.size() < 2) return; // если лист менее чем из 2х элементов - задача решена
for(int i = 1; i < a.size(); i++) { // длина всего этого дела равна длине листа, нулевой элемент оставляем, т.к. его не с чем сравнивать
Comparable b = (Comparable)a.remove(i); // получаем элемент который будем вставлять и заодно удаляем его со старого места в листе
int j = -1;
int l = 0; // левая граница бинарного поиска
int r = i; // правая граница
while (l <= r) { // тут в цикле сам поиск, в котором собственно и проблема. описание проблемы см. после кода
j = (l + r) / 2;
if(b.compareTo( (Comparable) a.get(j) ) == 0) break;
if(b.compareTo( (Comparable) a.get(j) ) > 0) l = j + 1;
else r = j - 1;
}
a.add(j, b);
}
return;
}
|
Так вот проблема такова - есть лист из N элементов. Их надо отсортировать вставкой. Во вставке есть место, где надо найти индекс куда вставлять элемент, так вот этот индекс надо найти при помощи бинарного поиска. Т.е. это уже не поиск получается, а что-то другое, т.к. необязательно, что в листе будет равный элемент.
Криво объяснил, но всё-же - как найти индекс куда вставлять элемент бинарным поиском, если искомый эдемент не обязательно сожержится в уже отсортированном листе?
На примере - есть у нас отсортированный рая чисел 1, 4, 5, 7, 10. Нам надо вставить туда 6 между 5 и 7. Индекс куда всявлять = 3. как найти этот индекс бинарным поиском. Вотъ. (примеры желательно на Java / C++, хотя и другие подойдут  ) |
