Почему это работает
- Ответ — первый индекс, где число не меньше искомого: само искомое, если оно есть, или следующее за ним большее. Если все числа меньше, это место за концом, поэтому hi начинается с len(nums).
- Если nums[mid] < target, место правее mid: lo = mid + 1. Иначе mid сам может оказаться этим местом, и hi = mid оставляет его в диапазоне.
- Всё до lo меньше искомого, а всё начиная с hi — нет. Когда lo встречает hi, эта граница и есть ответ, нашлось число или нет.
Сложность
Время O(log n): каждый шаг делит диапазон мест пополам. Память O(1): три индекса.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗