Давайте рассмотрим 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. Создайте указатель влево на 1.
  2. Создайте указатель вправо на n.
  3. Создайте цикл while для перемещения указателей.
  4. Внутри цикла найдите середину массива. Назовите его середина.
  5. Если isBadVersion не mid, переместите левый указатель вперед.
  6. Если isBadVersion имеет значение mid, правый указатель становится mid.
  7. Выйдите из цикла while.
  8. вернуть левый указатель (поскольку оба указателя теперь относятся к одному и тому же целому числу).

Код

Удачного кодирования!