Нужно ли для этого искать b-дерево?

Question

У меня есть массив целых чисел, которые могут встречаться в сотнях тысяч (или более), отсортированных по возрастанию, так как они были изначально сложены.

Мне нужно иметь возможность запросить массив кполучить индекс его первого появления числа >= некоторого ввода, настолько эффективно, насколько это возможно.Единственный способ узнать, как это сделать, даже не задумываясь об этом, - это перебирать массив, проверяя условие, пока оно не вернет 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

Помещение этих данных в БД для выполнения этого поиска будет только последним средством, так как я стремлюсь увидеть какой-то алгоритмчтобы быстро решить эту проблему в памяти.

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

Сейчас я думаю "B-Tree", ноесли честно, я бы понятия не имел, как его реализовать, и прежде чем я уйду и начну разбираться с этим, мне интересно, есть ли хороший алгоритм, который лучше подходит для этого единственного варианта использования?

Answer 1

Вы должны использовать бинарный поиск . Цель C могла бы даже иметь встроенный метод для этого (многие языки, которые я знаю, делают). B-дерево, вероятно, не сильно поможет, если вы не хотите хранить данные на диске.

Answer 2

Я не знаю о Objective-C, но C (обычный C) поставляется с функцией с именем bsearch (кроме того, AFAIK, Obj-C может вызывать функции C просто отлично):

http://www.cplusplus.com/reference/clibrary/cstdlib/bsearch/

Это в основном выполняет бинарный поиск, который звучит так, как будто это то, что вам нужно.

Answer 3

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

Я думаю, что btree, вероятно, излишне ...

Answer 4

Линейный поиск, также называемый последовательным поиском, просматривает каждый элемент в последовательности с самого начала, чтобы увидеть, присутствует ли нужный элемент в структуре данных.Когда объем данных невелик, этот поиск выполняется быстро. Это просто, но необходимая работа пропорциональна количеству данных, которые необходимо найти. Удвоение количества элементов удвоит время поиска, если требуемый элемент отсутствует.1001 *

Двоичный поиск эффективен для большого массива.В этом мы проверяем средний элемент. Если значение больше того, что мы ищем, то посмотрите в первой половине, иначе посмотрите во второй половине.Повторяйте это, пока нужный предмет не будет найден.Таблица должна быть отсортирована для бинарного поиска.Это исключает половину данных на каждой итерации. Ее логарифмическая

Answer 5

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