Pythonの最初の悪いバージョン

ある会社で、ある製品マネージャーが新製品を開発するチームを率いているとします。最新バージョンが品質チェックに失敗したとします。各バージョンは前のバージョンに基づいて開発されているため、不良バージョン以降のすべてのバージョンが不良になります。したがって、n個の要素[1、2、…n]を持つ配列Aがあり、この配列から最初の不良バージョンを見つける必要があります。

関数isBadVersion（version_id）があるとすると、これはバージョンが悪いかどうかを返します。たとえば、n =5で、バージョン=4が最初の不良バージョンであるとします。したがって、isBadVersion（3）がfalseを返し、isBadVersion（5）がtrueを返し、isBadVersion（4）もtrueを返す場合、最初の不良バージョンは4です

これを解決するには、次の手順に従います-

• n <2の場合、nを返します
• 指定された関数を使用して不良バージョンを検出するために、バイナリ検索アプローチを実行します。

例

理解を深めるために、次の実装を見てみましょう-

first_bad = 0
def isBadVersion(version):
   if version >= first_bad:
      return True
   return False
class Solution:
   def firstBadVersion(self, n):
      if n <2:
         return n
      start = 1
      end = n
      while(start<=end):
         mid = (start+end)//2
         if isBadVersion(mid) and not isBadVersion(mid-1):
            return mid
         elif isBadVersion(mid-1):
            end = mid-1
         else:
            start = mid+1
ob1 = Solution()
first_bad = 4
op = ob1.firstBadVersion(5)
print(op)

入力

5
4

出力

4