Единственный ресурс, где сказано, что все основано на уравнении прямой. В остальных источниках отрывочные сведения. Хотя сама идея не сложная, собрать воедино все самому не просто
24:00 17-ая строка и весь if вокруг неё не имеют же смысла: она никогда не выполнится при тех условиях, что заложены в обрамляющем for(..) из 16й строки: for(..) просто не пустит в своё тело, когда область поиска сузится до одного элемента. Т.е. проверка в 16й строке всегда автоматом выполняет проверку и из 17й строки для отсортированного☝🏼 массива как у нас в задаче. Дядь Саша, согласны?
Александр добрый день, Интерполяционный поиск он не работает с большими массивами данных получается, просто я попробовал с массивом на 100_000_000 элементов, найти в этом массиве 99_000_000 элемент, точнее его индекс, и при помощи данного поиска это сделать не получается, выходит что Интерполяционный поиск рассчитан на работу с небольшими массивами. Просто я пробовал на маленьком массиве, использовать данный поиск, работает без проблем, а если массив с большим количеством элементов, то программа очень долго думает, я так и не дождался пока найдётся искомый элемент
Нет. Алгоритм интерполяционного поиска подходит для массивов любого размера. Так, что все должно работать. Пришлите ваш код попробую разобраться в чем тут дело.
О спасибо вам за этот вопрос. Благодаря ему я нашел небольшой баг в коде на Java. Алгоритм универсальный, а вот переполнение типа int в Java никто не отменял :). Вот и получилось, что на массивах больших размеров получаем переполнение индекса. Нужно было поменять тип выражения на long, а потом опять привести к int. Этот код будет работать для массивов любых размеров. private static int interpolationSearch(int[] sequence, int searchElement) { int l = 0; // нулевой индекс в массиве int r = sequence.length - 1; // последний индекс в массиве for (; sequence[l] < searchElement && searchElement < sequence[r];) { if (sequence[l] == sequence[r]) { break; } // вычисляем индекс искомого элемента по формуле int index = (int) ((searchElement - sequence[l]) * 1L * (l - r) / (sequence[l] - sequence[r]) + l); if (sequence[index] > searchElement) { r = index - 1; } else if (sequence[index] < searchElement) { l = index + 1; } else { return index; } }
@@oleksandrtsymbaliuk спасибо большое, код работает. Но как так получилось что я вышел за пределы диапазона int - ведь там массив на 100_000_000 - элементов, это даже не близко к выходу за пределы диапазона int, предел int - это вроде 2_000_000_000 с копейками
А проблема была в этой строке: (searchElement - sequence[l]) * (l - r) на 0 элемента стоит число 1, вот и получим значение (99_000_000 -1)*(0-99_999_999) что при умножении даст нам значение больше чем int (и как следствие переполнение). Ну и после этого, уже "посыпались" дальнейшие вычисления индекса.
А это как говорится любимый предмет спора если скучно. Я бы мог возразить например так - Изначально язык назывался Oak («Дуб»), разрабатывался Джеймсом Гослингом для программирования бытовых электронных устройств. Из-за того, что язык с таким названием уже существовал, Oak был переименован в Java. Назван в честь марки кофе Java, которая, в свою очередь, получила наименование одноимённого острова (Ява), поэтому на официальной эмблеме языка изображена чашка с горячим кофе. Т.е. названия острова Ява (вот прям официально) язык назван в честь сорта кофе, который назван в честь острова. Но как по мне это не принципиально.
Ну так вы вместо выхода из метода поставили вывод индекса на экран. У вас вот так else { System.out.print(index); } Но это не закончит цикл и не закончит метод, вот вы и получили свой бесконечный цикл. А в моем коде вот так else { return index; } И оператор return закончит метод (и цикл соответственно) в это ми причина
![Алгоритмы Поиска Пути на Python. Алгоритм А*, Дейкстры, Поиск в ширину [ Pygame ]](http://i.ytimg.com/vi/xXvNDrF4obQ/mqdefault.jpg)
Ваш канал - открытие для меня. Большое спасибо за труд и такую подачу материала. Вы достойны восхищения, жму руку))
Это гениальный контент! Сколько перерыл видео на ютюбе, так круто никто не объясняет!
Уникальный и полезный контент. Спасибо за труд.
Спасибо, помогло разобраться как работает этот поиск
Я рад что эта лекция помогла вам.
Единственный ресурс, где сказано, что все основано на уравнении прямой. В остальных источниках отрывочные сведения. Хотя сама идея не сложная, собрать воедино все самому не просто
Ооо, за всякие человеческие пожелания в конце урока отдельная благодарность:)👍🏼👍🏼👍🏼 А то уже подзапаривает всё это дело.
Спасибо! Очень наглядно
побольше таких видео)
Постараюсь создать действительно побольше таких видео.
❤
24:00
17-ая строка и весь if вокруг неё не имеют же смысла: она никогда не выполнится при тех условиях, что заложены в обрамляющем for(..) из 16й строки: for(..) просто не пустит в своё тело, когда область поиска сузится до одного элемента.
Т.е. проверка в 16й строке всегда автоматом выполняет проверку и из 17й строки для отсортированного☝🏼 массива как у нас в задаче. Дядь Саша, согласны?
А точно. Действительно, этот условный оператор можно удалить.
Александр добрый день, Интерполяционный поиск он не работает с большими массивами данных получается, просто я попробовал с массивом на 100_000_000 элементов, найти в этом массиве 99_000_000 элемент, точнее его индекс, и при помощи данного поиска это сделать не получается, выходит что Интерполяционный поиск рассчитан на работу с небольшими массивами. Просто я пробовал на маленьком массиве, использовать данный поиск, работает без проблем, а если массив с большим количеством элементов, то программа очень долго думает, я так и не дождался пока найдётся искомый элемент
Нет. Алгоритм интерполяционного поиска подходит для массивов любого размера. Так, что все должно работать. Пришлите ваш код попробую разобраться в чем тут дело.
@@oleksandrtsymbaliuk
//точка входа
public static void main(String[] args) {
int[] arr = IntStream.rangeClosed(1, 100_000_000).toArray();
int searchElement = 99_000_000;
int index = interpolationSearch(arr, searchElement);
System.out.println(index);
}
private static int interpolationSearch(int[] sequence, int searchElement){
int l = 0; // нулевой индекс в массиве
int r = sequence.length - 1; //последний индекс в массиве
for(;sequence[l] < searchElement && searchElement < sequence[r];){
if(sequence[l] == sequence[r]){
break;
}
//вычисляем индекс искомого элемента по формуле
int index = (searchElement - sequence[l])*(l - r) / (sequence[l] - sequence[r]) + l;
if(sequence[index] > searchElement){
r = index - 1;
}else if(sequence[index] < searchElement){
l = index + 1;
}else {
return index;
}
}
if(sequence[l] == searchElement){
return l;
}
if(sequence[r] == searchElement){
return r;
}
return -1;
}
О спасибо вам за этот вопрос. Благодаря ему я нашел небольшой баг в коде на Java. Алгоритм универсальный, а вот переполнение типа int в Java никто не отменял :). Вот и получилось, что на массивах больших размеров получаем переполнение индекса. Нужно было поменять тип выражения на long, а потом опять привести к int. Этот код будет работать для массивов любых размеров.
private static int interpolationSearch(int[] sequence, int searchElement) {
int l = 0; // нулевой индекс в массиве
int r = sequence.length - 1; // последний индекс в массиве
for (; sequence[l] < searchElement && searchElement < sequence[r];) {
if (sequence[l] == sequence[r]) {
break;
}
// вычисляем индекс искомого элемента по формуле
int index = (int) ((searchElement - sequence[l]) * 1L * (l - r) / (sequence[l] - sequence[r]) + l);
if (sequence[index] > searchElement) {
r = index - 1;
} else if (sequence[index] < searchElement) {
l = index + 1;
} else {
return index;
}
}
@@oleksandrtsymbaliuk спасибо большое, код работает. Но как так получилось что я вышел за пределы диапазона int - ведь там массив на 100_000_000 - элементов, это даже не близко к выходу за пределы диапазона int, предел int - это вроде 2_000_000_000 с копейками
А проблема была в этой строке:
(searchElement - sequence[l]) * (l - r)
на 0 элемента стоит число 1, вот и получим значение (99_000_000 -1)*(0-99_999_999) что при умножении даст нам значение больше чем int (и как следствие переполнение). Ну и после этого, уже "посыпались" дальнейшие вычисления индекса.
Извините за простоту, и нубизм, но "Java" -> "Джава" но не "Ява", например "Joker" -> "Джокер" но не "Ёкер" или "Якер"
А это как говорится любимый предмет спора если скучно. Я бы мог возразить например так - Изначально язык назывался Oak («Дуб»), разрабатывался Джеймсом Гослингом для программирования бытовых электронных устройств. Из-за того, что язык с таким названием уже существовал, Oak был переименован в Java. Назван в честь марки кофе Java, которая, в свою очередь, получила наименование одноимённого острова (Ява), поэтому на официальной эмблеме языка изображена чашка с горячим кофе. Т.е. названия острова Ява (вот прям официально) язык назван в честь сорта кофе, который назван в честь острова. Но как по мне это не принципиально.
@@oleksandrtsymbaliuk Согласен, о вкусах не спорят.
Бесконечній цикл у меня получается
Покажите ваш код, и попробуем разобраться в чем проблема.
@@oleksandrtsymbaliuk
public static void interpolitionSearch(int [] Mass2, int element2) {
int l = 0;
int r = Mass2.length - 1;
for (; Mass2[l] < element2 && element2 < Mass2[r]; ) {
if(Mass2[l] == Mass2[r]){
break;
};
int index = (element2 - Mass2[l]) * (l - r) / (Mass2[l] - Mass2[r]) + l;
if(Mass2[index] > element2){
r = index - 1;
}else if(Mass2[index] < element2){
l = index + 1;
}else{
System.out.print(index);
};
};
if(Mass2[l]==element2){
System.out.print(l);
};
if(Mass2[r]==element2){
System.out.print(r);
};
};
Ну так вы вместо выхода из метода поставили вывод индекса на экран. У вас вот так
else {
System.out.print(index);
}
Но это не закончит цикл и не закончит метод, вот вы и получили свой бесконечный цикл.
А в моем коде вот так
else {
return index;
}
И оператор return закончит метод (и цикл соответственно) в это ми причина
@@oleksandrtsymbaliuk Понял. Спасибо большое!