35 LeetCode Бинарный поиск без боли | Search Insert Position | lowerBound в чистом виде | JavaScript

Leetcode задача: https://leetcode.com/problems/search-insert-position/description/ Гитхаб: https://github.com/qa-tester22/Algorithms-and-Data-Structures/blob/main/1_hw_leetcode_35_search_insert_position.js телеграм обсуждения: https://t.me/qa_english_time Мой Литкод: https://leetcode.com/u/qatester22/ Задача выглядит простой, но здесь есть классная идея в том, что мы не просто ищем target, а находим место, куда его нужно вставить, чтобы массив остался отсортированным. Это ровно паттерн Lower Bound | первый индекс, где nums[i] больше или равно target. Мы решаем задачу за O(log n) с помощью бинарного поиска и аккуратных границ. Тут важный инсайт - мы ищем не “есть ли число”, а “где оно должно лежать”. То есть ответ существует всегда, даже если target нет в массиве. И это идеально решается одним бинарным поиском, который возвращает точку вставки. Трюк 1. В этой задаче нет варианта ‘не найдено’ как -1 или null. Если числа нет, ты всё равно обязан вернуть индекс, куда его вставить. Трюк 2. Нам нужен первый индекс, где значение НЕ меньше target, то есть nums[i] больше или равно target. Трюк 3. Так как значения distinct, нет проблемы диапазона. В отличие от LeetCode 34, где два бинпоиска. 35. Search Insert Position 35. Поиск. Вставка позиции. Сложность решения задачи получилось: Time: O(log n) Space: O(1) решения домашних задач есть на гитхабе https://github.com/qa-tester22/Algorithms-and-Data-Structures/ и на моём литкоде https://leetcode.com/u/qatester22/ Хороших решений! #leetcode, #binarysearch, #lowerbound #javascript #interviewpreparation , #dsa, #arrays, #codinginterview #algorithms #linearsearch #алгоритмы #бинарныйпоиск #линейныйпоиск #javascript #джаваскрипт #информатика