int getRightBorder(vector<int>& nums, int target) { int left = 0; int right = nums.size() - 1; int rightBorder = -2; // 记录一下rightBorder没有被赋值的情况 while (left <= right) { int middle = left + ((right - left) / 2); if (nums[middle] > target) { right = middle - 1; } else { // 寻找右边界,nums[middle] == target的时候更新left left = middle + 1; rightBorder = left; } } return rightBorder; }分析一下这段代码
时间: 2024-02-14 08:33:23 浏览: 26
这段代码是一个二分查找的算法,用于查找一个有序数组中指定元素的右边界位置。具体来说,它使用了一个while循环,不断缩小搜索范围,直到找到目标元素的右边界位置或者搜索范围为空。其中,变量left和right分别表示搜索范围的左右边界位置,rightBorder表示目标元素的右边界位置,初始值为-2代表没有找到目标元素。
在每次循环中,首先计算出中间位置middle,然后判断nums[middle]与目标元素target的大小关系。若nums[middle] > target,则说明目标元素在左半部分数组中,将搜索范围缩小为[left, middle-1];否则,目标元素在右半部分数组中,将搜索范围缩小为[middle+1, right]。在这个过程中,如果遇到nums[middle]==target的情况,说明当前middle位置可能是目标元素的右边界位置,但不能确定,因为右边还有可能有target元素,所以需要继续在右半部分数组中查找。为了找到目标元素的右边界位置,每次更新left时,将rightBorder置为left。当while循环结束时,rightBorder即为目标元素的右边界位置,如果没有找到目标元素,则返回-2。
相关问题
int binarySearch(vector<int>& nums, int target, bool lower) { int left = 0, right = (int)nums.size() - 1, ans = (int)nums.size(); while (left <= right) { int mid = (left + right) / 2; if (nums[mid] > target || (lower && nums[mid] >= target)) { right = mid - 1; ans = mid; } else { left = mid + 1; } } return ans; } int search(vector<int>& nums, int target) { int leftIdx = binarySearch(nums, target, true); int rightIdx = binarySearch(nums, target, false) - 1; if (leftIdx <= rightIdx && rightIdx < nums.size() && nums[leftIdx] == target && nums[rightIdx] == target) { return rightIdx - leftIdx + 1; } return 0; } 详细解释代码
这段代码实现了在有序数组中查找某个元素的出现次数。
函数 `binarySearch` 是一个二分查找函数,其中 `nums` 是有序数组,`target` 是目标值,`lower` 表示是否查找第一个大于等于目标值的元素。如果 `lower` 为 true,则查找第一个大于等于目标值的元素,否则查找第一个大于目标值的元素。如果找到了符合条件的元素,则返回其下标;否则,返回数组的长度。
函数 `search` 利用 `binarySearch` 函数分别查找目标值在有序数组中第一次和最后一次出现的位置,然后计算出现次数。具体步骤如下:
1. 调用 `binarySearch(nums, target, true)` 查找目标值第一次出现的位置,保存在变量 `leftIdx` 中。
2. 调用 `binarySearch(nums, target, false) - 1` 查找目标值最后一次出现的位置,然后减 1,保存在变量 `rightIdx` 中。
3. 如果目标值在数组中出现过,并且第一次和最后一次出现的位置都找到了,则返回它们之间的元素个数,即 `rightIdx - leftIdx + 1`。
4. 如果目标值在数组中没有出现过,则返回 0。
值得注意的是,这段代码中的二分查找算法是一个通用的模板,可以用来查找大于等于或大于目标值的元素位置。同时,二分查找的时间复杂度为 O(log n),比暴力查找的时间复杂度 O(n) 要快得多。
class Solution { public: int searchInsert(vector<int>& nums, int target) { } };
nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
};
// Time Complexity: O(log n)
// Space Complexity: O(1)
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)