First Bad Version

Problem

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.

Examples

Example 1:

1
2
3
4
5
6
7
8
9


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:

1
2
3
4


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

Solution

Method 1 – Recursive Binary Search

Intuition

Since all versions after the first bad version are also bad, we can use binary search to efficiently find the first bad version. At each step, we check the middle version:

If it is bad, the first bad version must be at or before this version.
If it is not bad, the first bad version must be after this version. We recursively narrow the search range until we find the first bad version.

Approach

Start with the full range of versions [1, n].
At each step, compute the middle version mid.
If isBadVersion(mid) is true, search the left half (including mid).
If not, search the right half (excluding mid).
When the range narrows to a single version, return it as the answer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


// The API isBadVersion(version) is defined for you.
class Solution {
public:
	int firstBadVersion(int n) {
		return helper(1, n);
	}
	int helper(int left, int right) {
		if (left >= right) return left;
		int mid = left + (right - left) / 2;
		if (isBadVersion(mid)) return helper(left, mid);
		else return helper(mid + 1, right);
	}
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


// The isBadVersion API is defined for you.
func firstBadVersion(n int) int {
	var helper func(left, right int) int
	helper = func(left, right int) int {
		if left >= right {
			return left
		}
		mid := left + (right-left)/2
		if isBadVersion(mid) {
			return helper(left, mid)
		}
		return helper(mid+1, right)
	}
	return helper(1, n)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


// The isBadVersion API is defined for you.
public class Solution extends VersionControl {
	public int firstBadVersion(int n) {
		return helper(1, n);
	}
	private int helper(int left, int right) {
		if (left >= right) return left;
		int mid = left + (right - left) / 2;
		if (isBadVersion(mid)) return helper(left, mid);
		else return helper(mid + 1, right);
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


// The isBadVersion API is defined for you.
open class VersionControl {
	fun isBadVersion(version: Int): Boolean = TODO()
}
class Solution : VersionControl() {
	fun firstBadVersion(n: Int): Int {
		fun helper(left: Int, right: Int): Int {
			if (left >= right) return left
			val mid = left + (right - left) / 2
			return if (isBadVersion(mid)) helper(left, mid) else helper(mid + 1, right)
		}
		return helper(1, n)
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:
class Solution:
	def firstBadVersion(self, n: int) -> int:
		def helper(left, right):
			if left >= right:
				return left
			mid = left + (right - left) // 2
			if isBadVersion(mid):
				return helper(left, mid)
			else:
				return helper(mid + 1, right)
		return helper(1, n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


// The is_bad_version API is defined for you.
// fn is_bad_version(version: i32) -> bool;
impl Solution {
	pub fn first_bad_version(n: i32) -> i32 {
		fn helper(left: i32, right: i32) -> i32 {
			if left >= right {
				return left;
			}
			let mid = left + (right - left) / 2;
			if is_bad_version(mid) {
				helper(left, mid)
			} else {
				helper(mid + 1, right)
			}
		}
		helper(1, n)
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


// The isBadVersion API is defined for you.
function firstBadVersion(n: number): number {
	function helper(left: number, right: number): number {
		if (left >= right) return left;
		const mid = Math.floor(left + (right - left) / 2);
		if (isBadVersion(mid)) return helper(left, mid);
		else return helper(mid + 1, right);
	}
	return helper(1, n);
}

Complexity

⏰ Time complexity: O(log n), since we halve the search space at each step.
🧺 Space complexity: O(log n), due to the recursion stack.

Method 2 – Iterative Binary Search

Intuition

Instead of recursion, we can use an iterative approach to binary search. We maintain two pointers (left and right) and repeatedly check the middle version. If the middle version is bad, we record it as a candidate and continue searching to the left. If not, we search to the right. This approach avoids recursion and uses constant space.

Approach

Initialize left = 1, right = n, and ans = -1.
While left <= right:
- Compute mid = left + (right - left) / 2.
- If isBadVersion(mid) is true:
  - Record mid as the current answer.
  - Move right to mid - 1 to search for an earlier bad version.
- Else, move left to mid + 1 to search for a later bad version.
Return ans as the first bad version.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


// The API isBadVersion(version) is defined for you.
class Solution {
public:
	int firstBadVersion(int n) {
		int left = 1, right = n, ans = -1;
		while (left <= right) {
			int mid = left + (right - left) / 2;
			if (isBadVersion(mid)) {
				ans = mid;
				right = mid - 1;
			} else {
				left = mid + 1;
			}
		}
		return ans;
	}
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


// The isBadVersion API is defined for you.
func firstBadVersion(n int) int {
	left, right, ans := 1, n, -1
	for left <= right {
		mid := left + (right-left)/2
		if isBadVersion(mid) {
			ans = mid
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


// The isBadVersion API is defined for you.
public class Solution extends VersionControl {
	public int firstBadVersion(int n) {
		int left = 1, right = n, ans = -1;
		while (left <= right) {
			int mid = left + (right - left) / 2;
			if (isBadVersion(mid)) {
				ans = mid;
				right = mid - 1;
			} else {
				left = mid + 1;
			}
		}
		return ans;
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


// The isBadVersion API is defined for you.
open class VersionControl {
	fun isBadVersion(version: Int): Boolean = TODO()
}
class Solution : VersionControl() {
	fun firstBadVersion(n: Int): Int {
		var left = 1
		var right = n
		var ans = -1
		while (left <= right) {
			val mid = left + (right - left) / 2
			if (isBadVersion(mid)) {
				ans = mid
				right = mid - 1
			} else {
				left = mid + 1
			}
		}
		return ans
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:
class Solution:
	def firstBadVersion(self, n: int) -> int:
		left, right, ans = 1, n, -1
		while left <= right:
			mid = left + (right - left) // 2
			if isBadVersion(mid):
				ans = mid
				right = mid - 1
			else:
				left = mid + 1
		return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


// The is_bad_version API is defined for you.
// fn is_bad_version(version: i32) -> bool;
impl Solution {
	pub fn first_bad_version(n: i32) -> i32 {
		let (mut left, mut right, mut ans) = (1, n, -1);
		while left <= right {
			let mid = left + (right - left) / 2;
			if is_bad_version(mid) {
				ans = mid;
				right = mid - 1;
			} else {
				left = mid + 1;
			}
		}
		ans
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


// The isBadVersion API is defined for you.
function firstBadVersion(n: number): number {
	let left = 1, right = n, ans = -1;
	while (left <= right) {
		const mid = Math.floor(left + (right - left) / 2);
		if (isBadVersion(mid)) {
			ans = mid;
			right = mid - 1;
		} else {
			left = mid + 1;
		}
	}
	return ans;
}

Complexity

⏰ Time complexity: O(log n), since we halve the search space at each step.
🧺 Space complexity: O(1), since we use only a constant amount of extra space.

Problem#

Examples#

Solution#

Method 1 – Recursive Binary Search#

Intuition#

Approach#

Code#

Complexity#

Method 2 – Iterative Binary Search#

Intuition#

Approach#

Code#

Complexity#

Problem

Examples

Solution

Method 1 – Recursive Binary Search

Intuition

Approach

Code

Complexity

Method 2 – Iterative Binary Search

Intuition

Approach

Code

Complexity