LeetCode - Easy - 278. First Bad Version

Love The Way You Lie 2023-01-10 10:08 127阅读 0赞

## Topic ##

*  Binary Search

## Description ##

[https://leetcode.com/problems/first-bad-version/][https_leetcode.com_problems_first-bad-version]

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 <= 2³¹ - 1

## Analysis ##

略

## Submission ##

class VersionControl{ 
    
    	public static int badVersion;
    	
    	public boolean isBadVersion(int version) { 
    		return version >= badVersion;
    	}
    }
    
    public class FirstBadVersion extends VersionControl{ 
    
    	public int firstBadVersion(int n) { 
    		int left = 1, right = n;
    		
    		while(left < right) { 
    			int mid = left + (right - left) / 2;
    			
    			if(isBadVersion(mid)) { 
    				right = mid;
    			}else { 
    				left = mid + 1;
    			}
    		}
    		
            return right;
        }
    }

## Test ##

import static org.junit.Assert.*;
    import org.junit.Test;
    
    public class FirstBadVersionTest { 
    
    	@Test
    	public void test() { 
    		FirstBadVersion obj = new FirstBadVersion();
    		VersionControl.badVersion = 4;
    		assertEquals(4, obj.firstBadVersion(5));
    		
    		VersionControl.badVersion = 1;
    		assertEquals(1, obj.firstBadVersion(1));
    	}
    }

[https_leetcode.com_problems_first-bad-version]: https://leetcode.com/problems/first-bad-version/