Поиск целого числа k в отсортированном массиве за время O (log (m)), где m - количество элементов перед k? - PullRequest
Новая
       10

Поиск целого числа k в отсортированном массиве за время O (log (m)), где m - количество элементов перед k?

0 голосов
/ 25 апреля 2020

Моему классу было дано следующее задание:

Найти алгоритм, который получает отсортированный массив и целое число k в качестве параметров и возвращает index of k в массиве , Если k не находится в массиве, вернуть -1.

Пока все хорошо. Вот где я застрял:

Требование сложности времени: O (log (m)) , где m - количество элементов перед k. Если k отсутствует в массиве, m - это число элементов перед ближайшим к k элементом.

Подсказка: Шаги поиска должны расти в геометрической прогрессии, не обязательно начиная с середины.

Каждый из нас должен реализовывать один и тот же алгоритм на разных языках, поэтому мне бы хотелось получить объяснение псевдокода, поскольку оно очень помогло бы мне объяснить его друзьям. Второй приоритет - Java.

Ответы [ 2 ]

1 голос
/ 25 апреля 2020

Во-первых, давайте попробуем определить диапазон, в котором k может быть как можно меньше. Мы будем смотреть на элементы a[0], a[1], a[2], ... a[2 ** i], ..., пока не найдем элемент, который больше k. Предположим, мы остановились на индексе r. Тогда мы точно знаем, что, поскольку массив отсортирован, если k находится в массиве, его позиция m меньше r. Другим фактом, который имеет решающее значение для сложности времени, является то, что m > i/2. Это верно, потому что на предыдущем шаге мы смотрели на a[r/2], и оно было меньше, чем k.

Если мы запустим простой двоичный поиск для подмассива a[0 ... r], мы найдем k в O(log r). Общее количество шагов для поиска r было O(log r). Так как r > m > r/2 это правда, что log r > log m > log r - 1. Поэтому мы можем переписать O(log r) как O(log m), и это именно то, что нам нужно.

Это мое решение в Python 3: 

def find(a, k):
    if a[0] > k:
        return -1

    r = 1
    while r < len(a):
        if a[r] > k:
            break
        r *= 2

    if r >= len(a):
        if a[-1] < k:
            return -1
        r = len(a) - 1

    l = -1
    while r - l > 1:
        m = (l + r) // 2
        if a[m] < k:
            l = m
        else:
            r = m

    if a[r] == k:
        return r   
    else:
        return -1
1 голос
/ 25 апреля 2020

Вы ищете Экспоненциальный поиск .

В Экспоненциальном поиске мы прыгаем индексы с 0 в степени 2 до достижения индекса со значением выше, чем искомое число , т.е. допустим, что число находится в индексе 14, мы переходим к индексу 16 и останавливаемся, поскольку число в 16-м индексе больше нашего числа. Сложность по времени составляет O(log m), так как мы останавливаем момент, когда мы передаем m на степени 2.

Чем мы выполняем двоичный поиск между 0 и индексом, на котором мы остановились на предыдущем шаге. Почему? Поскольку теперь между нижней и верхней границами не более 2 м чисел, поэтому временная сложность двоичного поиска составляет O(log (2m)), что составляет O(log m), и все готово!

Псевдокод: 

exponential_search:
 Array A 
 Key k

1. i = 1
2. while A[i - 1] < k and i <= size of A
2.1.  i = i * 2

// Now i is no more than 2 * m

3. perform binary search with k and A between 0 and i
4. return the binary search's result
...