共计 690 个字符,预计需要花费 2 分钟才能阅读完成。
左闭右开写法
- 查找某个元素是否呈现。
int binarySearch(vector<int>& nums, int target)
{
int left = 0;
int right= nums.size();
int mid = 0;
//[left, mid) mid [mid+1, right)
while(left< right)
{mid = (right - left) / 2 + left;
if(nums[mid] == target) return mid;
if(nums[mid] < target) left = mid + 1;
if(nums[mid] > target) right = mid;
}
return -1; // 未找到 target
}
- 查找第一个大于或等于某个元素的地位
int lowerBound(vector<int> &nums, int target) {
int left = 0;
int right = nums.size();
int mid = 0;
while(left < right)
{mid = (right - left) / 2 + left;
if (nums[mid] >= target) {right = mid;} else {left = mid + 1;}
}
return left;
}
- 查找第一个大于某个元素的地位。
int upperBound(vector<int> &nums, int target) {
int left = 0;
int right = nums.size();
int mid = 0;
while(left < right)
{mid = (right - left) / 2 + left;
if (nums[mid] > target) {right = mid;} else {left = mid + 1;}
}
return left;
}
正文完