У меня есть массив целых чисел, который может набирать сотни тысяч (или больше), отсортированных по возрастанию, так как они были изначально сложены.Нужно ли мне реализовать поиск по дереву?
Мне нужно иметь возможность запросить массив, чтобы получить индекс его первого вхождения числа >= с некоторым вводом, насколько это возможно. Единственный способ, которым я мог бы это сделать, даже не думая об этом, - это перебрать массив, проверяющий условие до тех пор, пока он не вернет true, после чего я прекратил бы итерацию. Однако это самое дорогое решение этой проблемы, и я ищу лучший алгоритм для ее решения.
Я кодирую Objective-C, но я приведу пример в JavaScript, чтобы расширить аудиторию людей, которые могут ответить.
// Sample set
var numbers = [1, 7, 23, 23, 23, 89, 1002, 1003];
var indexAfter100 = getIndexOfValueGreaterThan(100);
var indexAfter7 = getIndexOfValueGreaterThan(7);
// (indexAfter100 == 6) == true
// (indexAfter7 == 2) == true
Ввод этих данных в БД, чтобы выполнить этот запрос будет только последним средством решения, так как я заинтересован, чтобы увидеть какой-то алгоритм для решения этой быстро в памяти.
У do есть возможность изменить структуру данных или сохранить дополнительную структуру данных при создании массива, так как моя программа уже вытолкнула каждый номер один за другим в этот стек, d просто измените код, добавляющий их в стек. Поиск индекса по мере добавления в стек невозможно, так как операция поиска будет повторяться часто с разными значениями после факта.
Сейчас я думаю «B-Tree», но, честно говоря, я бы понятия не имел, как реализовать его, и до того, как я уйду и начну понимать это, интересно, есть ли хороший алгоритм, который подходит для этого один вариант использования лучше?
Спасибо. Читая это сейчас. – d11wtq
Это так просто, и это именно тот алгоритм, который я искал, спасибо. Теперь я просто пинаю себя, что это не появилось в моей голове несколько часов назад! :П – d11wtq