Нахождение, суммируют ли два элемента в предварительном сортированном массиве для равенства определенному значению
Я работаю над проблемой домашней работы, и я испытываю некоторые затруднения при создании O (n*logn) решение. Я должен записать функцию, которая берет предварительный сортированный массив и значение для поиска. Я затем должен найти, суммируют ли какие-либо два элемента массива для равенства тому значению.
Я должен создать и O (n) и O (n*logn) алгоритмы для этого.
O (n) было легко создать; однако, я испытываю затруднения при создании O (n*logn) алгоритм, не добавляя в некотором бесплатном коде, который на самом деле не помогает в решении проблемы. Если кто-либо мог бы дать мне некоторые подсказки по тому, что я мог бы пропускать, это будет цениться.
2 ответа
Начать с первого элемента и идти последовательно. При этом ищите второй элемент с помощью бинарного поиска.
«Когда у вас слишком много таблиц?»
На уровне логического оформления правильный ответ - «никогда».
На уровне физического дизайна (поскольку «наличие таблицы» действительно относится к какому-то понятию, которое относится к физическому дизайну) правильный ответ заключается в том, «если и когда запросы, которые вам необходимо сделать, учитывая ограничения используемой СУБД, приводят к неприемлемо низкому исполнительный».
-121--2643505-Начните с первого элемента и последовательно. При этом искать второй элемент с помощью двоичного поиска.
-121--5044501-Поскольку они предварительно отсортированы, можно использовать двоичный поиск и линейный поиск