yoruru的努力日記

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Example 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.

Example 2:

Input: n = 1, bad = 1
Output: 1

Constraints:

• 1 <= bad <= n <= 231 - 1

SOL：

懂了 binary search 的概念，做過了第 69 題 Sqrt(x)，這一題很容易想出解法。

最耗時間的反而是讀懂題目，我都寫完code了，才發現我把 isBadVersion 這個function的意思搞反了。

一樣給定 1~n 這個範圍，從中選數字(mid)丟進去call isBadVersion。

若 false，代表到mid為止都不是BadVersion，則搜尋範圍調整成 (mid+1)~end。

若 true，代表mid之後都是BadVersion，無需考慮，則搜尋範圍在前面，調整成 sart~mid。

Note: python 的布林值是 True 跟 False，無論是全大寫或全小寫，系統都判別不出來。

因為mid有可能是最初的BadVersion，因此必須把mid列入考量，不可像 上一篇 一樣用(mid-1)。

此外，while 的終止條件也必須把 start 跟 end 相等拿掉，否則while迴圈會無法終止。

雖然都是binary search 的題目，但必須依題意做些微的調整，如果用之前的程式照抄，會是錯的。

Reference：

LeetCode-278. First Bad Version