278. 第一个错误的版本

问题278 第一个错误的版本 ★☆☆☆☆

https://leetcode-cn.com/problems/first-bad-version/

这个题目是二分查找的变种，相比问题35稍微难一点点，在二分查找的基础上稍作修改即可。值得注意的地方是，这里二分查找的循环条件是low < high，而不是low <= high，注意体会为什么是这样。其实也很好理解，把握住循环不变量是什么就可以了：在循环过程中，low是非错误的版本，high始终是错误的版本。最终会达到low和high相邻，此时high恰好是第一个错误的版本。

	public int firstBadVersion(int n) {
		assert n >= 1;

		int low = 1, high = n;
		while (low < high) {
			int mid = low + (high - low)/2;
			if (isBadVersion(mid)) {
				high = mid;
			} else {
				low = mid + 1;
			}
		}

		return high;
	}

在 LeetCode 查看