Tag Archives: 二分搜索

LeetCode Find K Closest Elements

LeetCode Find K Closest Elements
Given a sorted array, two integers k and x, find the k closest elements to x in the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred.
Example 1:

Input: [1,2,3,4,5], k=4, x=3
Output: [1,2,3,4]

Example 2:

Input: [1,2,3,4,5], k=4, x=-1
Output: [1,2,3,4]

Note:

  1. The value k is positive and will always be smaller than the length of the sorted array.
  2. Length of the given array is positive and will not exceed 104
  3. Absolute value of elements in the array and x will not exceed 104

给定一个有序数组,要从中找出k个和x最接近的元素,按升序排列输出。
首先在有序数组中用二分查找找到x的lowerbound,如果lowerbound指向begin(),则取开头k个元素即可;如果lowerbound指向end(),则取末尾k个元素;否则,令left指向lowerbound-1,right指向lowerbound,每次取left、right中和x差值最小的那个数,直到取够k个为止。最后对结果数组排序。
完整代码如下:

class Solution {
public:
	vector<int> findClosestElements(vector<int>& arr, int k, int x) {
		vector<int> ans;
		int n = arr.size();
		auto it = lower_bound(arr.begin(), arr.end(), x);
		if (it == arr.begin()) {
			while (ans.size() < k) {
				ans.push_back(*it++);
			}
			return ans;
		}
		else if (it == arr.end()) {
			while (ans.size() < k) {
				ans.push_back(*--it);
			}
			return ans;
		}
		else {
			int right = it - arr.begin();
			int left = right - 1;
			int left_diff = INT_MAX, right_diff = INT_MAX;
			while (ans.size() < k) {
				if (left >= 0)left_diff = abs(arr[left] - x);
				else left_diff = INT_MAX;
				if (right < n)right_diff = abs(arr[right] - x);
				else right_diff = INT_MAX;
				if (left_diff <= right_diff) {
					ans.push_back(arr[left]);
					--left;
				}
				else {
					ans.push_back(arr[right]);
					++right;
				}
			}
		}
		sort(ans.begin(), ans.end());
		return ans;
	}
};

本代码提交AC,用时143MS。

LeetCode Minimum Size Subarray Sum

LeetCode Minimum Size Subarray Sum
Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn't one, return 0 instead.
For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.

click to show more practice.

More practice:If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).

给定一个正整数数组和一个数s,要求从数组中找出最短的子串,使得子串的和大于等于s。
解法1,双指针法,O(n)。维护两个指针left和right,初始时都为0,我们的目标就是使[left,right)的和大于等于s。所以先right右移,直到和大于等于s,此时尝试缩小区间,即left也右移,在右移的过程中,更新最短子串长度,且累加和要减去left指向的数。这样不断的先移right,后移left,并更新最短长度。
代码如下,非常简洁易懂。

class Solution {
public:
	int minSubArrayLen(int s, vector<int>& nums) {
		int n = nums.size(), left = 0, right = 0, sum = 0, ans = INT_MAX;
		while(right < n) {
			while (right < n&&sum < s)sum += nums[right++];
			while (left <= right&&sum >= s) {
				ans = min(ans, right - left);
				sum -= nums[left++];
			}
		}
		return ans == INT_MAX ? 0 : ans;
	}
};

本代码提交AC,用时13MS。
解法2,二分查找,O(nlgn)。我们先想想暴力方法,枚举每个left,从left开始枚举right,直到累加和第一次超过sum,更新最短长度。这样两层循环,时间复杂度是O(n^2)的。有没有办法把内层查找right的时间复杂度降低呢?
遇到子数组和的问题,马上要想到借助累加和数组。所以我们先求到原数组的累加和数组accuSum[n+1],其中accuSum[i]等于原数组中前i-1个数之和。我们利用accuSum来循环right,对于每个left,它要找一个right,使得left和right之间的和大于等于s,也就相当于在accuSum中找一个right,使得accuSum[right]>=accuSum[left]+s,等价于accuSum[right]-accuSum[left]>=s,即left到right的累加和大于等于s。因为原数组是正整数数组,所以accuSum是递增有序的,所以我们可以在accuSum中二分查找。即查找right的复杂度降为了O(lgn),所以总的复杂度就是O(nlgn)了。
完整代码如下:

class Solution {
private:
	int searchRight(vector<int>& accuSum, int l, int r, int target) {
		while (l <= r) {
			int m = l + (r - l) / 2;
			if (accuSum[m] == target)return m;
			else if (accuSum[m] > target)r = m - 1;
			else l = m + 1;
		}
		return l;
	}
public:
	int minSubArrayLen(int s, vector<int>& nums) {
		int n = nums.size(), ans = INT_MAX;
		vector<int> accuSum(n + 1, 0);
		for (int i = 1; i <= n; ++i)accuSum[i] = accuSum[i - 1] + nums[i - 1];
		for (int left = 0; left < n; ++left) {
			int right = searchRight(accuSum, left, accuSum.size() - 1, accuSum[left] + s);
			if (right == n + 1)break;
			ans = min(ans, right - left);
		}
		return ans == INT_MAX ? 0 : ans;
	}
};

本代码提交AC,用时16MS。

LeetCode Kth Smallest Element in a Sorted Matrix

LeetCode Kth Smallest Element in a Sorted Matrix
Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.
Note that it is the kth smallest element in the sorted order, not the kth distinct element.
Example:

matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,
return 13.

Note:
You may assume k is always valid, 1 ≤ k ≤ n2.


给定一个矩阵,该矩阵每行和每列都是有序的,要找出第k小的数。
如果只利用每行或者每列是有序的,则可以使用堆解决。我们以行为例,那么每行都是有序的,则相当于把所有行进行n路归并,然后找到第k小的数。所以我们构建一个最小堆,首先把所有行的首元素放到堆中,然后n路归并k次,每次弹出堆顶元素(即当前最小值),然后把原堆顶元素所在行的下一个元素放入堆中。k次归并结束之后,堆顶元素即为第k小的元素。
代码如下:

class Solution {
private:
	struct Node {
		int val, row, col;
		Node(int v = 0, int r = 0, int c = 0) :val(v), row(r), col(c) {};
		friend bool operator<(const Node& n1, const Node& n2) {
			return n1.val > n2.val;
		}
	};
public:
	int kthSmallest(vector<vector<int>>& matrix, int k) {
		int n = matrix.size();
		priority_queue<Node> pn;
		for (int i = 0; i < n; ++i)pn.push(Node(matrix[i][0], i, 0));
		Node t;
		while (k--) {
			t = pn.top();
			pn.pop();
			if (t.col < n - 1)pn.push(Node(matrix[t.row][t.col + 1], t.row, t.col + 1));
		}
		return t.val;
	}
};

本代码提交AC,用时45MS。时间复杂度是O(klgn),堆的大小为n,每次归并调整堆需要lgn时间,一共需要归并k次,所以总的时间复杂度是O(klgn)。
另外用二分的方法可以同时利用行有序和列有序的特点。这种矩阵可以看成一个曲面,曲面的最低点为左上角元素left,最高点为右下角元素right,所以曲面就是从左上角向上延伸到右下角(想象一下MATLAB画的图)。那么第k小的数肯定在[left,right]范围内,我们可以二分查找这个区间。假设中点是mid,则我们在每一行找找比mid小的数有多少个,加起来如果等于cnt,则说明mid这个数排在第cnt位。因为每一行也是有序的,所以可以直接用upper_bound查找第一个比mid大的数。
代码如下:

class Solution {
public:
	int kthSmallest(vector<vector<int>>& matrix, int k) {
		int n = matrix.size(), left = matrix[0][0], right = matrix[n - 1][n - 1];
		while (left <= right) {
			int mid = left + (right - left) / 2;
			int cnt = 0;
			for (int i = 0; i < n; ++i) {
				cnt += upper_bound(matrix[i].begin(), matrix[i].end(), mid) - matrix[i].begin();
			}
			if (cnt < k)left = mid + 1;
			else right = mid - 1;
		}
		return left;
	}
};

本代码提交AC,用时43MS。时间复杂度是O(lgX nlgn),X为[left,right]的区间大小,ngln是对于每个mid,都需要在每一行二分查找比mid小的数的个数。
还可以将上述复杂度降为O(lgX n)。就是在找cnt,不需要每一行都二分查找,我们可以从矩阵的左下角往右上角阶梯查找,如果要查找的数更大,则往右移,否则往上移,每次查询只需要O(n)的时间,所以总时间是O(lgX n)。
代码如下:

class Solution {
private:
	int count_less_equal(vector<vector<int>>& matrix, int num) {
		int n = matrix.size(), i = n - 1, j = 0, cnt = 0;
		while (i >= 0 && j < n) {
			if (matrix[i][j] <= num) {
				cnt += i + 1;
				++j;
			}
			else --i;
		}
		return cnt;
	}
public:
	int kthSmallest(vector<vector<int>>& matrix, int k) {
		int n = matrix.size(), left = matrix[0][0], right = matrix[n - 1][n - 1];
		while (left <= right) {
			int mid = left + (right - left) / 2;
			int cnt = count_less_equal(matrix, mid);
			if (cnt < k)left = mid + 1;
			else right = mid - 1;
		}
		return left;
	}
};

本代码提交AC,用时39MS。

LeetCode Heaters

LeetCode Heaters
Winter is coming! Your first job during the contest is to design a standard heater with fixed warm radius to warm all the houses.
Now, you are given positions of houses and heaters on a horizontal line, find out minimum radius of heaters so that all houses could be covered by those heaters.
So, your input will be the positions of houses and heaters seperately, and your expected output will be the minimum radius standard of heaters.
Note:

  1. Numbers of houses and heaters you are given are non-negative and will not exceed 25000.
  2. Positions of houses and heaters you are given are non-negative and will not exceed 10^9.
  3. As long as a house is in the heaters' warm radius range, it can be warmed.
  4. All the heaters follow your radius standard and the warm radius will the same.

Example 1:

Input: [1,2,3],[2]
Output: 1
Explanation: The only heater was placed in the position 2, and if we use the radius 1 standard, then all the houses can be warmed.

Example 2:

Input: [1,2,3,4],[1,4]
Output: 1
Explanation: The two heater was placed in the position 1 and 4. We need to use radius 1 standard, then all the houses can be warmed.

给定房子和加热器的位置,问加热器的最小半径是所少才能使所有房子都在加热的范围之内。一个加热器的加热范围是一个圆,所有加热器的加热半径都是一样的。
要保证每个房子都在加热范围之内,且加热器的半径最小,则房子i肯定被紧邻i前后的两个加热器之一覆盖,其他加热器距离i的距离肯定比紧邻i前后的两个加热器远。比如x, i, y,i表示房子坐标,x和y分别表示紧邻i的两个加热器坐标,则覆盖i的最小半径应该是min(i-x,y-i)。
所以问题就转换为对每个房子坐标i,去加热器坐标数组中找到紧邻i前后的两个加热器坐标x和y,然后根据上述公式更新结果。为了便于查找,先对加热器坐标排序,然后直接二分查找就好了。
代码如下:

class Solution {
public:
	int findRadius(vector<int>& houses, vector<int>& heaters) {
		sort(heaters.begin(), heaters.end());
		int ans = 0;
		for (int i = 0; i < houses.size(); ++i) {
			int &pos = houses[i];
			int r = INT_MAX;
			auto lb = lower_bound(heaters.begin(), heaters.end(), pos);
			if (lb > heaters.begin())r = min(r, pos - *(lb - 1));
			auto ub = lower_bound(heaters.begin(), heaters.end(), pos);
			if (ub < heaters.end())r = min(r, *ub - pos);
			ans = max(ans, r);
		}
		return ans;
	}
};

本代码提交AC,用时89MS。
还可以自己写二分查找代码,如下:

class Solution {
private:
	int my_lower_bound(vector<int>& v, int target) {
		int l = 0, r = v.size() - 1;
		while (l <= r) {
			int m = l + (r - l) / 2;
			if (target > v[m])l = m + 1;
			else r = m - 1;
		}
		return l;
	}
public:
	int findRadius(vector<int>& houses, vector<int>& heaters) {
		sort(heaters.begin(), heaters.end());
		int ans = 0, n = houses.size(), m = heaters.size();
		for (int i = 0; i < n; ++i) {
			int &pos = houses[i];
			int r = INT_MAX;
			int lb = my_lower_bound(heaters, pos);
			if (lb > 0)r = min(r, pos - heaters[lb - 1]);
			if (lb < m)r = min(r, heaters[lb] - pos);
			ans = max(ans, r);
		}
		return ans;
	}
};

本代码提交AC,用时76MS。

LeetCode H-Index II

LeetCode H-Index II
Follow up for H-Index: What if the citations array is sorted in ascending order? Could you optimize your algorithm?
Hint:

  1. Expected runtime complexity is in O(log n) and the input is sorted.

LeetCode H-Index的延伸,如果citations是按升序排列的,怎样把算法优化到O(logn)。看到O(logn),马上想到二分查找。
首先左右边界是0和n-1,判断中点的citations[m]和n-m,如果正好相等,则说明正好有n-m篇大于等于n-m引用的文章,所以H-index为n-m。如果citations[m]>n-m,说明引用很大,h-index还能往上涨,所以中心点需要左移,即r=m-1。反之则中心点右移l=m+1。
代码如下:

class Solution {
public:
	int hIndex(vector<int>& citations) {
		int l = 0, n = citations.size(), r = n - 1;
		while (l <= r) {
			int m = l + (r - l) / 2;
			if (n - m == citations[m])return n - m;
			else if (citations[m] > n - m)r = m - 1;
			else l = m + 1;
		}
		return n - l;
	}
};

本代码提交AC,用时9MS。
我一开始的代码是,如果citations[m]<n-m,中心点确实右移了,即l=m+1。但是当citations[m]>n-m时,我没想到用r=m-1来左移中心点,误以为r一直都是n-1是固定的,所以这个时候使用了一个while循环来线性查找正确的m,理论上性能要比上面的纯二分差。
代码如下:

class Solution {
public:
	int hIndex(vector<int>& citations) {
		int l = 0, r = citations.size() - 1, n = citations.size();
		if (n == 0)return 0;
		if (citations[0] >= n)return n;
		while (l < r) {
			int m = l + (r - l) / 2;
			if (n - m>citations[m])l = m + 1;
			else {
				while (m > 0 && n - m <= citations[m])--m;
				return n - m - 1;
			}
		}
		if (citations[r] >= 1)return 1;
		else return 0;
	}
};

本代码提交AC,用时也是9MS。

LeetCode Find Right Interval

LeetCode Find Right Interval
Given a set of intervals, for each of the interval i, check if there exists an interval j whose start point is bigger than or equal to the end point of the interval i, which can be called that j is on the "right" of i.
For any interval i, you need to store the minimum interval j's index, which means that the interval j has the minimum start point to build the "right" relationship for interval i. If the interval j doesn't exist, store -1 for the interval i. Finally, you need output the stored value of each interval as an array.
Note:

  1. You may assume the interval's end point is always bigger than its start point.
  2. You may assume none of these intervals have the same start point.

Example 1:

Input: [ [1,2] ]
Output: [-1]
Explanation: There is only one interval in the collection, so it outputs -1.

Example 2:

Input: [ [3,4], [2,3], [1,2] ]
Output: [-1, 0, 1]
Explanation: There is no satisfied "right" interval for [3,4].
For [2,3], the interval [3,4] has minimum-"right" start point;
For [1,2], the interval [2,3] has minimum-"right" start point.

Example 3:

Input: [ [1,4], [2,3], [3,4] ]
Output: [-1, 2, -1]
Explanation: There is no satisfied "right" interval for [1,4] and [3,4].
For [2,3], the interval [3,4] has minimum-"right" start point.

给定一系列区间[start,end],定义区间[i,j]的“右区间”为[u,v]使得u是第一个不小于j的数。要求输出每个区间的右区间下标,如果不存在右区间,则输出-1。
我的解法。因为要输出右区间在原数组中的下标,所以得保留每个区间在原数组中的下标。定义一个新的结构体MyInterval,用来保存区间以及该区间在原数组中的下标。对所有区间按start排序,然后遍历每一个区间[i,j],在已排序区间数组中找第一个start大于j的区间,取出它的下标作为区间[i,j]的结果。
代码如下:

typedef struct MyInterval {
	Interval inter;
	int idx;
	MyInterval(Interval inter_, int idx_) :inter(inter_), idx(idx_) {};
	bool operator<(const MyInterval& myi) const{
		return this->inter.start < myi.inter.start; // 所有start不相同
	}
};
class Solution2 {
public:
	vector<int> findRightInterval(vector<Interval>& intervals) {
		int n = intervals.size();
		vector<MyInterval> myvs;
		for (int i = 0; i < n; ++i) {
			MyInterval myint(intervals[i], i);
			myvs.push_back(myint);
		}
		sort(myvs.begin(), myvs.end());
		vector<int> ans(n, -1);
		for (int i = 0; i < n; ++i) {
			for (int j = i + 1; j < n; ++j) { // 线性查找
				if (myvs[j].inter.start >= myvs[i].inter.end) {
					ans[myvs[i].idx] = myvs[j].idx;
					break;
				}
			}
		}
		return ans;
	}
};

本代码提交AC,用时299MS。
上述代码还可优化,在已排序区间数组中找第一个start大于j的区间时,可以用二分搜索。
另外因为所有区间的start不相同,所以事先用hash记录start和原数组下标。这样只需要把所有区间的start抽出来排序,然后二分查找每一个end。代码如下:

class Solution {
private:
	int binsearch(const vector<int>& starts, int target) {
		int l = 0, r = starts.size() - 1;
		while (l <= r) {
			int m = l + (r - l) / 2;
			if (starts[m] == target)return starts[m];
			if (starts[m] < target)l = m + 1;
			else r = m - 1;
		}
		return starts[l];
	}
public:
	vector<int> findRightInterval(vector<Interval>& intervals) {
		int n = intervals.size();
		vector<int> starts;
		unordered_map<int, int> hash;
		for (int i = 0; i < n; ++i) {
			starts.push_back(intervals[i].start);
			hash[intervals[i].start] = i;
		}
		sort(starts.begin(), starts.end());
		vector<int> ans(n, -1);
		for (int i = 0; i < n; ++i) {
			if (intervals[i].end <= starts[n - 1]) {
				int t = binsearch(starts, intervals[i].end);
				ans[i] = hash[t];
			}
		}
		return ans;
	}
};

本代码提交AC,用时96MS,快了不少。

LeetCode Summary Ranges

LeetCode Summary Ranges
Given a sorted integer array without duplicates, return the summary of its ranges.
For example, given [0,1,2,4,5,7], return ["0->2","4->5","7"].


给定一个数组,把数组汇总成若干个连续的区间,以字符串的形式给出。
方法是判断两个相邻的数之差是否为1,不是1则前面的构成一个区间,转换为字符串输出。判断前一个区间只有一个数还是有多个数的方法是区间的起止位置i,j是否相差1,如果是,则只有一个数,否则有多个数。
注意最后一个区间需要在while循环外部判断。代码如下:

class Solution {
public:
	vector<string> summaryRanges(vector<int>& nums) {
		vector<string> ans;
		int n = nums.size(), i = 0, j = 1;
		if (n == 0)return ans;
		while (j < n) {
			if (nums[j] - nums[j - 1] == 1) ++j;
			else {
				if (j - i == 1)ans.push_back(to_string(nums[i]));
				else ans.push_back(to_string(nums[i]) + "->" + to_string(nums[j - 1]));
				i = j++;
			}
		}
		if (j - i == 1)ans.push_back(to_string(nums[i]));
		else ans.push_back(to_string(nums[i]) + "->" + to_string(nums[j - 1]));
		return ans;
	}
};

本代码提交AC,用时0MS。
还有一种解法利用了二分查找的思路,很有意思,参考讨论区
假如给定的数组是[1,2,3,4,5,...,10000,20000],如果还是用上述方法,时间复杂度是O(n),至少需要遍历一遍数组。但是数组的前10000个数是严格有序且连续递增的,如果能把这一部分识别出来,直接转换为"1->10000",则速度会大大提高。
二分查找的思路是,对于给定区间[a,...,b],假设其在数组中的下标起点分别为[i,...,j],则如果b-a==j-i,说明[a,b]之间是类似上面的[1,2,...,10000]的情况的,因为数组中没有重复元素,所以区间有j-i个元素,且元素最大值和最小值的差b-a也是j-i,说明他们是一个连续的有序区间,我们直接把这个区间转换为"a->b"。
否则如果j-i!=b-a,则取中点mid=(i+j)/2,递归在[i,mid]和[mid+1,j]进行。
有一种情况需要注意的是,分割出来的区间可能需要合并,比如[1,2,3,4,5,6,8],初始i[1,..,8]不满足b-a==j-i,所以递归在[1,2,3,4]和[5,6,8]进行。左边转换为了"1->4",右边还需要递归,假设转换为了"5->6"和"8",那么"1->4"和"5->6"是需要合并的。所以我们在插入"5->6"时,看看之前得到的区间"1->4"的end是否和当前区间"5->6"的start只差1,如果是,则需要合并,更新之前区间的end为现在要插入区间的end,变成了"1->6"。
完整代码如下:

class Solution {
private:
	struct Range {
		int start, end;
		Range(int s, int e) :start(s), end(e) {};
	};
	void add2Ans(int a, int b, vector<Range>& ranges) {
		if (ranges.empty() || ranges[ranges.size() - 1].end != a - 1) {
			ranges.push_back(Range(a, b));
		}
		else {
			ranges[ranges.size() - 1].end = b;
		}
	}
	void helper(vector<int>& nums, int start, int end, vector<Range>& ranges) {
		if (start == end || end - start == nums[end] - nums[start]) {
			add2Ans(nums[start], nums[end], ranges);
			return;
		}
		int mid = start + (end - start) / 2;
		helper(nums, start, mid, ranges); // 先左区间
		helper(nums, mid + 1, end, ranges); // 后右区间
	}
public:
	vector<string> summaryRanges(vector<int>& nums) {
		vector<string> ans;
		if (nums.empty())return ans;
		vector<Range> ranges;
		helper(nums, 0, nums.size() - 1, ranges);
		for (const auto& r : ranges) {
			if (r.start == r.end)ans.push_back(to_string(r.start));
			else ans.push_back(to_string(r.start) + "->" + to_string(r.end));
		}
		return ans;
	}
};

本代码提交AC,用时0MS。
这个代码在数据有很多连续区间时,接近O(lgn)的复杂度。但是当数据全是不连续的时,比如[1,3,5,7,9],则只有到递归到最深层start==end(即针对单个数字)时,才得到一个区间,所以退化为O(n)的算法。
如果再follow up可能有重复元素时,上述二分查找的方法就不管用了,因为属于一个区间的不一定满足b-a==j-i,比如[1,2,2,2,3],b-a=2,而j-i=4。此时只能用第一种O(n)的方法:

class Solution {
public:
	vector<string> summaryRanges(vector<int>& nums) {
		vector<string> ans;
		if (nums.empty())return ans;
		int i = 0, j = 1, n = nums.size();
		while (j < n) {
			while (j < n && (nums[j] == nums[j - 1] || nums[j] - nums[j - 1] == 1))++j; // 考虑重复元素
			if (j >= n)break;
			if (j - 1 == i)ans.push_back(to_string(nums[i]));
			else ans.push_back(to_string(nums[i]) + "->" + to_string(nums[j - 1]));
			i = j++;
		}
		if (j - 1 == i)ans.push_back(to_string(nums[i]));
		else ans.push_back(to_string(nums[i]) + "->" + to_string(nums[j - 1]));
		return ans;
	}
};

本代码提交AC,用时0MS。

LeetCode First Bad Version

LeetCode 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 will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.


从[1,2,...,n]有n个版本,其中有个版本是坏的,导致其后的所有版本都是坏的,现在要找到第一个坏了的版本。
简单题,二分搜索,相当于找lowerbound,正好刷了LeetCode Search for a Range,理清了二分搜索查找上下界的方法,此题直接实现lowerbound就好。代码如下:

// Forward declaration of isBadVersion API.
bool isBadVersion(int version);
class Solution {
public:
	int firstBadVersion(int n) {
		int l = 1, r = n;
		while (l <= r) {
			int m = l + (r - l) / 2;
			if (!isBadVersion(m))l = m + 1;
			else r = m - 1;
		}
		return l;
	}
};

本代码提交AC,用时0MS。

LeetCode Search for a Range

LeetCode Search for a Range
Given an array of integers sorted in ascending order, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].


本题要在一个有序数组中求一个数出现的下标区间,如果该数不在数组中,返回[-1,-1],要求用O(lgn)时间复杂度。
很明显用两次二分搜索找到该数的上下区间即可,可以认为是二分搜索的综合题。下界就是第一个不小于target的位置,所以当找到中间值和target相等时,我们要继续往左找。上界就是最后一个不大于target的位置,所以当找到中间值和target相等时,我们要继续往右找。理清了这个思路之后就很好写代码了,如下:

class Solution {
private:
	int lowerbound(vector<int>& nums, int target) {
		int l = 0, r = nums.size() - 1;
		while (l <= r) {
			int m = l + (r - l) / 2;
			if (nums[m] < target)l = m + 1;
			else if (nums[m] >= target)r = m - 1;
		}
		return l;
	}
	int upperbound(vector<int>& nums, int target) {
		int l = 0, r = nums.size() - 1;
		while (l <= r) {
			int m = l + (r - l) / 2;
			if (nums[m] <= target)l = m + 1;
			else if (nums[m] > target)r = m - 1;
		}
		return r;
	}
public:
	vector<int> searchRange(vector<int>& nums, int target) {
		int lower = lowerbound(nums, target), upper = upperbound(nums, target);
		if (lower <= upper)return vector<int>({ lower, upper });
		else return vector<int>({ -1,-1 });
	}
};

本代码提交AC,用时9MS。
注意一点,为啥lowerbound是返回l,而upperbound是返回r呢,对于lowerbound,我们想象一下当中值等于target时,我们不停的往左走,即r=m-1,直到l<=r不再满足,即此时r已经小于l了,也就是说r往左走过头了,使得r对应的值已经小于target了,但此时l对应的值还是等于target,所以根据lowerbound的定义,我们返回l。对于uppperbound也类似,当中值等于target时,不停往右走,即l=m+1,直到不满足l<=r,此时l对应的值已经大于target,而r对应的值还是等于target的,根据upperbound的定义,我们返回r。
其实,STL中已经实现了lower_boundupper_bound其lower_bound和上文的lowerbound含义是一致的,upper_bound稍有不同,STL中的upper_bound是返回第一个大于target的位置,比上文的upperbound要大一个位置。所以如果借助STL的算法,需要对upper_bound返回的位置减1。代码如下:

class Solution {
public:
	vector<int> searchRange(vector<int>& nums, int target) {
		if (nums.size() == 0)return vector<int>({ -1,-1 });
		vector<int>::iterator lower = lower_bound(nums.begin(), nums.end(), target), upper = upper_bound(nums.begin(), nums.end(), target) - 1;
		if (lower <= upper)return vector<int>({ lower - nums.begin(), upper - nums.begin() });
		else return vector<int>({ -1,-1 });
	}
};

本代码提交AC,用时16MS。貌似STL中的实现也是O(lgn)的,看来性能还是有所差别。

LeetCode Guess Number Higher or Lower

LeetCode Guess Number Higher or Lower
We are playing the Guess Game. The game is as follows:
I pick a number from 1 to n. You have to guess which number I picked.
Every time you guess wrong, I'll tell you whether the number is higher or lower.
You call a pre-defined API guess(int num) which returns 3 possible results (-1, 1, or 0):

-1 : My number is lower
 1 : My number is higher
 0 : Congrats! You got it!

Example:

n = 10, I pick 6.
Return 6.

简单的猜数字游戏。使用二分搜索就好。唯一需要注意的是,题目中的guess函数中说My number is lower/higher是指正确答案比中值低或高,而不是我们猜的中值比正确答案低或高。唉,这算是题目描述不清吧,为此WA两次。
代码如下:

int guess(int num);
class Solution {
public:
	int guessNumber(int n) {
		int l = 1, r = n, mid = l + (r - l) / 2;
		int g = guess(mid);
		while (g != 0) {
			if (g == -1)r = mid - 1;
			else l = mid + 1;
			mid = l + (r - l) / 2;
			g = guess(mid);
		}
		return mid;
	}
};

本代码提交AC,用时0MS。