Учитывая битномический массив и элемент x в массиве, найдите индекс x в 2log (n) времени
Сначала битонный массив для этого вопроса определяется как один такой, что для некоторого индекса K в массиве длины N, где 0 < K < N - 1 и от 0 до K - монотонно возрастающая последовательность целых чисел, а K - N - 1 - монотонно убывающая последовательность целых чисел.
Пример: [1, 3, 4, 6, 9, 14, 11, 7, 2, -4, -9]. Он монотонно увеличивается от 1 до 14, затем уменьшается с 14 до -9.
Предшественником этого вопроса является его решение в 3log(n), что намного проще. Один измененный двоичный поиск, чтобы найти индекс max, затем два бинарных поиска для 0 до K и от K + 1 до N - 1 соответственно.
Я предполагаю, что решение в 2log(n) требует решения проблемы без нахождения индекса max. Я думал о перекрытии бинарных поисков, но помимо этого, я не уверен, как двигаться вперед.
Ответы
Ответ 1
Алгоритмы, представленные в других ответах (this и this), к сожалению, неверны, они не являются O (logN)!
Рекурсивная формула f (L) = f (L/2) + log (L/2) + c не приводит к f (L) = O (log (N)), но приводит к f (L) = O ((log (N)) ^ 2)!
Действительно, предположим, что k = log (L), то log (2 ^ (k-1)) + log (2 ^ (k-2)) +... + log (2 ^ 1) = log (2 ) * (k-1 + k-2 +... + 1) = O (k ^ 2). Следовательно, log (L/2) + log (L/4) +... + log (2) = O ((log (L) ^ 2)).
Правильный способ решения проблемы во времени ~ 2log (N) должен выполняться следующим образом (предполагая, что массив сначала в порядке возрастания, а затем в порядке убывания):
- Возьмите середину массива
- Сравните средний элемент с одним из его соседей, чтобы увидеть, находится ли макс справа или слева.
- Сравните средний элемент с желаемым значением
- Если средний элемент меньше желаемого значения, а max - с левой стороны, то выполните битномический поиск в левом подмассиве (мы уверены, что это значение не находится в правом подмассиве)
- Если средний элемент меньше желаемого значения, а max - с правой стороны, то выполните битонический поиск в правом подмассиве
- Если средний элемент больше желаемого значения, то выполните нисходящий двоичный поиск в правом подмассиве и восходящем двоичном поиске в левом подмассиве.
В последнем случае, возможно, было бы удивительно выполнить двоичный поиск в подмассиве, который может быть битным, но он действительно работает, потому что мы знаем, что элементы, которые находятся не в хорошем порядке, больше, чем требуемое значение. Например, выполнение возрастающего двоичного поиска значения 5 в массиве [2, 4, 5, 6, 9, 8, 7] будет работать, потому что 7 и 8 больше желаемого значения 5.
Ниже приведена полностью работающая реализация (на С++) битонического поиска во времени ~ 2logN:
#include <iostream>
using namespace std;
const int N = 10;
void descending_binary_search(int (&array) [N], int left, int right, int value)
{
// cout << "descending_binary_search: " << left << " " << right << endl;
// empty interval
if (left == right) {
return;
}
// look at the middle of the interval
int mid = (right+left)/2;
if (array[mid] == value) {
cout << "value found" << endl;
return;
}
// interval is not splittable
if (left+1 == right) {
return;
}
if (value < array[mid]) {
descending_binary_search(array, mid+1, right, value);
}
else {
descending_binary_search(array, left, mid, value);
}
}
void ascending_binary_search(int (&array) [N], int left, int right, int value)
{
// cout << "ascending_binary_search: " << left << " " << right << endl;
// empty interval
if (left == right) {
return;
}
// look at the middle of the interval
int mid = (right+left)/2;
if (array[mid] == value) {
cout << "value found" << endl;
return;
}
// interval is not splittable
if (left+1 == right) {
return;
}
if (value > array[mid]) {
ascending_binary_search(array, mid+1, right, value);
}
else {
ascending_binary_search(array, left, mid, value);
}
}
void bitonic_search(int (&array) [N], int left, int right, int value)
{
// cout << "bitonic_search: " << left << " " << right << endl;
// empty interval
if (left == right) {
return;
}
int mid = (right+left)/2;
if (array[mid] == value) {
cout << "value found" << endl;
return;
}
// not splittable interval
if (left+1 == right) {
return;
}
if(array[mid] > array[mid-1]) {
if (value > array[mid]) {
return bitonic_search(array, mid+1, right, value);
}
else {
ascending_binary_search(array, left, mid, value);
descending_binary_search(array, mid+1, right, value);
}
}
else {
if (value > array[mid]) {
bitonic_search(array, left, mid, value);
}
else {
ascending_binary_search(array, left, mid, value);
descending_binary_search(array, mid+1, right, value);
}
}
}
int main()
{
int array[N] = {2, 3, 5, 7, 9, 11, 13, 4, 1, 0};
int value = 4;
int left = 0;
int right = N;
// print "value found" is the desired value is in the bitonic array
bitonic_search(array, left, right, value);
return 0;
}
Ответ 2
Алгоритм работает рекурсивно, комбинируя битонные и бинарные поисковые запросы:
def bitonic_search (array, value, lo = 0, hi = array.length - 1)
if array[lo] == value then return lo
if array[hi] == value then return hi
mid = (hi + lo) / 2
if array[mid] == value then return mid
if (mid > 0 & array[mid-1] < array[mid])
| (mid < array.length-1 & array[mid+1] > array[mid]) then
# max is to the right of mid
bin = binary_search(array, value, low, mid-1)
if bin != -1 then return bin
return bitonic_search(array, value, mid+1, hi)
else # max is to the left of mid
bin = binary_search(array, value, mid+1, hi)
if bin != -1 then return bin
return bitonic_search(array, value, lo, mid-1)
Таким образом, рекурсивная формула для времени f(l) = f(l/2) + log(l/2) + c, где log(l/2) происходит из двоичного поиска, а c - это стоимость сравнений, выполненных в теле функции.
Ответ 3
public int FindLogarithmicGood(int value)
{
int lo = 0;
int hi = _bitonic.Length - 1;
int mid;
while (hi - lo > 1)
{
mid = lo + ((hi - lo) / 2);
if (value < _bitonic[mid])
{
return DownSearch(lo, hi - lo + 1, mid, value);
}
else
{
if (_bitonic[mid] < _bitonic[mid + 1])
lo = mid;
else
hi = mid;
}
}
return _bitonic[hi] == value
? hi
: _bitonic[lo] == value
? lo
: -1;
}
где DownSearch -
public int DownSearch(int index, int count, int mid, int value)
{
int result = BinarySearch(index, mid - index, value);
if (result < 0)
result = BinarySearch(mid, index + count - mid, value, false);
return result;
}
и BinarySearch
/// <summary>
/// Exactly log(n) on average and worst cases.
/// Note: System.Array.BinarySerch uses 2*log(n) in the worst case.
/// </summary>
/// <returns>array index</returns>
public int BinarySearch(int index, int count, int value, bool asc = true)
{
if (index < 0 || count < 0)
throw new ArgumentOutOfRangeException();
if (_bitonic.Length < index + count)
throw new ArgumentException();
if (count == 0)
return -1;
// "lo minus one" trick
int lo = index - 1;
int hi = index + count - 1;
int mid;
while (hi - lo > 1)
{
mid = lo + ((hi - lo) / 2);
if ((asc && _bitonic[mid] < value) || (!asc && _bitonic[mid] > value))
lo = mid;
else
hi = mid;
}
return _bitonic[hi] == value ? hi : -1;
}
github
Ответ 4
Ответы предоставленные имеют временную сложность (N/2) * logN. Потому что худший случай может включать слишком много подпросмотров, которые не нужны. Модификация заключается в сравнении целевого значения с левым и правым элементом подсерии перед поиском. Если целевое значение не находится между двумя концами монотонной серии или меньше обоих концов битной серии, последующий поиск является избыточным. Эта модификация приводит к сложности 2lgN.
Ответ 5
Существует 5 основных случаев, в зависимости от того, где находится максимальный элемент массива, и является ли средний элемент большим, чем желаемое значение
Вычислить средний элемент.
Сравните желаемое значение среднего элемента, если оно совпадает с поиском. В противном случае переходите к следующему шагу.
-
Сравните средний элемент с соседями, чтобы увидеть, находится ли элемент max слева или справа. Если оба из соседей меньше среднего элемента, тогда элемент отсутствует в массиве, следовательно, выйдите. (Массив, упомянутый в вопросе, сначала столкнется с этим случаем, так как 14, максимальный элемент находится в середине)
-
Если средний элемент меньше желаемого значения, а элемент max находится справа, выполните битномический поиск в правом подмассиве
-
Если средний элемент меньше желаемого значения, а элемент max находится слева, выполните битномический поиск в левом подмассиве
-
Если средний элемент больше желаемого значения, а элемент max находится слева, выполните нисходящий двоичный поиск в правом подмассиве
-
Если средний элемент больше желаемого значения, а элемент max находится справа, выполните восходящий двоичный поиск в левом подмассиве
В худшем случае мы будем делать два сравнения каждый раз, когда массив делится пополам, поэтому сложность будет 2 * logN
Ответ 6
Поиск изменения знака среди различий первого порядка, стандартным дихотомическим поиском, будет принимать обращения к массиву 2Lg(n).
Вы можете сделать немного лучше, используя стратегию поиска для максимальной унимодальной функции, известной как поиск Фибоначчи. После n шагов, каждый из которых включает один поиск, вы уменьшаете размер интервала на коэффициент Fn, соответствующий примерно Log n/Log φ ~ 1.44Lg(n), для доступа к максимальному значению.
Этот предельный выигрыш дает немного больше смысла, когда обращения к массиву являются более дорогостоящими оценками funciton.
Ответ 7
Для двоичного разбиения есть три случая:
- Максимальный элемент находится справа, затем двоичный поиск влево и прав поиска в биттонах.
- Максимальный элемент слева, затем правый двоичный поиск и поиск по битонику слева.
- max элемент находится в точке разделения точно, затем двоичный как слева, так и справа.
Предупреждение: двоичный поиск, используемый слева и справа, отличается тем, что увеличивается/уменьшается порядок.
public static int bitonicSearch(int[] a, int lo, int hi, int key) {
int mid = (lo + hi) / 2;
int now = a[mid];
if (now == key)
return mid;
// deal with edge cases
int left = (mid == 0)? a[mid] : a[mid - 1];
int right = (mid == a.length-1)? a[mid] : a[mid + 1];
int leftResult, rightResult;
if (left < now && now < right) { // max item is at right
leftResult = binarySearchIncreasing(a, lo, mid - 1, key);
if (leftResult != -1)
return leftResult;
return bitonicSearch(a, mid + 1, hi, key);
}
else if (left > now && now > right) { // max item is at left
rightResult = binarySearchDecreasing(a, mid + 1, hi, key);
if (rightResult != -1)
return rightResult;
return bitonicSearch(a, lo, mid - 1, key);
}
else { // max item stands at the split point exactly
leftResult = binarySearchIncreasing(a, lo, mid - 1, key);
if (leftResult != -1)
return leftResult;
return binarySearchDecreasing(a, mid + 1, hi, key);
}
}
