典型题目: 34. 在排序数组中查找元素的第一个和最后一个位置
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
if(nums.size() == 0) return {-1, -1};
return vector<int>{searchLeft(nums, target), searchRight(nums, target)};
}
// [a, a, a, b, b, b, c, c, c]
// [0, 1, 2, 3, 4, 5, 6, 7, 8]
// 找二段性数组的左边界，e.g. 下标为3，6的值
// 二分时，mid向下取整，偏left
// 对应地，left取mid+1，right取mid
// 循环结束标志为 left == right时，跳出循环后需要对left进行验证
int searchLeft(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
while(left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] >= target) {
right = mid;
}
else {
left = mid + 1;
}
}
return nums[left] == target ? left : -1;
}
// [a, a, a, b, b, b, c, c, c]
// [0, 1, 2, 3, 4, 5, 6, 7, 8]
// 找二段性数组的左边界，e.g. 下标为2，5的值
// 二分时，mid向上取整，偏right
// 对应地，left取mid，right取mid+1
// 循环结束标志为 left == right时，跳出循环后需要对left进行验证
int searchRight(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
while(left < right) {
int mid = left + (right - left + 1) / 2;
if (nums[mid] > target) {
right = mid - 1;
}
else {
left = mid;
}
}
return nums[left] == target ? left : -1;
}
};思维扩展题目：162. 寻找峰值
引用宫水三叶の相信科学系列】关于能够「二分」的两点证明中：最早在 33. 搜索旋转排序数组, 题解三叶公众号【面试高频系列】一道可以考察「二分」本质的面试题 中，我们强调，二分的本质是「二段性」而非「单调性」，而经过本题，我们进一步发现「二段性」还能继续细分，不仅仅只有满足 01 特性（满足/不满足）的「二段性」可以使用二分，满足 1? 特性（一定满足/不一定满足）也可以二分。
33. 搜索旋转排序数组
162. 寻找峰值
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[right]) {
left = mid + 1;
}else {
right = mid;
}
}
int k = left;
cout<<k<<endl;
// 0, k up; k + 1, n-1 up;
if (target >= nums[0] && k != 0) {
left = 0;
right = k;
}else{
left = k;
right = nums.size() - 1;
}
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
}
else if (nums[mid] < target) {
left = mid + 1;
}
else {
right = mid;
}
}
return nums[left] == target ? left : -1;
}
};评论 (0)
