binary_search模板

//取左中位数
int binary_search(vector<int> nums, int target) {
	int left = 0;
	int right = nums.size()-1;

	while (left < right) {
		int mid = left + (right - left) / 2;
		if (target > nums[mid]) {
			left = mid + 1;
		}
		else {
			right = mid;
		}
	}
	return left;
}
//取右中位数
int binary_search(vector<int> nums, int target) {
	int left = 0;
	int right = nums.size()-1;

	while (left < right) {
		int mid = left + (right - left) / 2 + 1;
		if (target < nums[mid]) {
			right = mid - 1;
		}
		else {
			left = mid;
		}
	}
	return left;
}

此模板中不对命中情况做特别判断。
取左中位数的情况下，命中target，只是将其作为right边界，这样最后获得的target位置为其相同元素的最左边。若数组中没有target，则会命中紧紧大于target的数，因为如果命中紧紧小于target的值，索引会加一。
取右中位数的情况相反。