Задача
Задача бинпоиска поиск первого/последнего вхождения элемента на отсортированном массиве.
Алгоритм
Сначала задаются границы поиска. Они ставятся за границы массива, левая граница (далее l) =-1, правая граница(далее r)=n(длина массива).
Далее вычисляем середину(далее mid) =(l+r)//2. Далее если элемент под индексом mid >искомого числа(далее х), то r=mid, иначе l=mid. Повторять пока r-l>1.(нахождение последнего вхождения)
Если l (по завершении работы )=x , то l последние вхождение элемента, иначе x в массиве нет.
Для поиска первого вхождения требуется заменить условие по изменению границ , на такие:"Далее если элемент под индексом mid < х, то l=mid, иначе r=mid. "
Ответом в данном случае будет r
Асимптотика
Поскольку данный алгоритм постоянно делит список на 2 части, то асимптотика - O(log2(n))
Код
Python
Последние вхождение https://drive.google.com/file/d/1i2eJhdQsmw1tEmzvR0XuBVCs2Zxrg-KZ/view?usp=sharing
Первое вхождение
https://drive.google.com/file/d/1GqFqNn5wulcKt6tI9ODGKAvb7oiUSejJ/view?usp=sharing