Давайте рассмотрим 14-дневный учебный план LeetCode по взлому алгоритма. Часть 2.
Проблема
Вы менеджер по продукту и в настоящее время возглавляете команду по разработке нового продукта. К сожалению, последняя версия вашего продукта не проходит проверку качества. Поскольку каждая версия разрабатывается на основе предыдущей версии, все версии после плохой версии тоже плохие.
Предположим, у вас есть n
версий [1, 2, ..., n]
и вы хотите узнать, какая из них первая плохая, из-за чего все последующие будут плохими.
Вам предоставляется API bool isBadVersion(version)
, который возвращает, является ли version
плохим. Реализуйте функцию для поиска первой плохой версии. Вы должны свести к минимуму количество обращений к API.
Пример 1:
Input: n = 5, bad = 4
Output: 4
Explanation:
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
Then 4 is the first bad version.
Пример 2:
Input: n = 1, bad = 1
Output: 1
Ограничения:
1 <= bad <= n <= 231 - 1
Решение
Эта проблема решается с помощью Двоичный поиск. Два указателя пересекают набор данных, чтобы найти первую неверную версию продукта.
- Создайте указатель влево на 1.
- Создайте указатель вправо на n.
- Создайте цикл while для перемещения указателей.
- Внутри цикла найдите середину массива. Назовите его середина.
- Если isBadVersion не mid, переместите левый указатель вперед.
- Если isBadVersion имеет значение mid, правый указатель становится mid.
- Выйдите из цикла while.
- вернуть левый указатель (поскольку оба указателя теперь относятся к одному и тому же целому числу).
Код
Удачного кодирования!