Эффективный способ подсчета вхождений ключа в отсортированном массиве

Об этом спрашивали в интервью на сайте Microsoft.

Подсчитайте количество вхождений данного ключа в массив.

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

Затем он спросил, а что, если массив отсортирован?

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

Верен ли мой анализ в обоих случаях?

Пример:

Input = [0 0 1 1 1 2 2 3 3], key = 1, Answer = 3
Input = [0 0 2 2 3 3],       key = 1, Answer = 0