vector实现二分查找
时间: 2023-10-22 13:03:46 浏览: 35
要使用vector实现二分查找,可以按照以下步骤进行操作:
1. 初始化左边界left为0,右边界right为vector的长度减1。
2. 在一个while循环中,判断left是否小于等于right。如果是,继续循环;如果不是,表示查找结束,返回right。
3. 在循环中,计算中间位置middle,可以使用(left + right) / 2或者(left + right) >> 1来避免整数溢出的问题。
4. 比较middle位置上的元素和目标值target的大小关系。
- 如果nums[middle]大于target,表示target在左区间,更新right为middle - 1,进入下一轮循环继续查找左区间。
- 如果nums[middle]小于target,表示target在右区间,更新left为middle + 1,进入下一轮循环继续查找右区间。
- 如果nums[middle]等于target,表示找到了目标值,直接返回middle作为结果。
5. 如果循环结束时仍未找到目标值,则根据不同情况返回right或者right + 1作为目标值的插入位置。
下面是一个使用vector实现二分查找的示例代码:
```cpp
int binarySearch(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
while (left <= right) {
int middle = left + (right - left) / 2;
if (nums[middle > target) {
right = middle - 1;
} else if (nums[middle < target) {
left = middle + 1;
} else {
return middle;
}
}
return right + 1;
}
```
这段代码可以在给定的有序vector nums中查找目标值target。如果找到目标值,则返回其下标;如果未找到,则返回目标值应该插入的位置。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* *2* *3* [二分法其实很简单,为什么老是写不对!!!](https://blog.csdn.net/youngyangyang04/article/details/105937425)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 100%"]
[ .reference_list ]