Алгоритм двоичного поиска

Question

Я использую бинарный поиск, чтобы найти запись. Мой вопрос не о том, есть ли данные или нет. Я перечислю свои вопросы ниже.

1. если данные в следующем порядке

1 2 3 4 4 5 5 5 6 7 8 8 9 10 11

Если сейчас я хочу найти 5, где он находится в первую очередь. Используя алгоритм двоичного поиска, я могу получить 5 или нет. в приведенном выше случае я могу получить 6-е место из 5 (всего 13 данных). Но мне нужно получить 5 место. Как я могу получить это с помощью бинарного поиска? Еще раз в некоторых случаях мне нужно получить последнюю позицию данных данных. Как я могу получить этот алгоритм двоичного поиска.

Есть ли самый быстрый метод, чем бинарный поиск? Нет, но метод хеширования?

Answer 1

Вы можете снова использовать бинарный поиск.

1. Чтобы получить наименьшее значение 5, снова начните поиск, но его верхние границы на 1 меньше текущего найденного значения 5.
2. Чтобы получить наибольшее значение 5, снова начните поиск, но его нижние границы 1 больше текущего найденного значения 5.

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