LeetCode 二分查找模板 II
2024-08-29 21:25:32
模板 #2：
int binarySearch(vector<int>& nums, int target){
if(nums.size() == 0)
return -1;
int left = 0, right = nums.size();
while(left < right){
// Prevent (left + right) overflow
int mid = left + (right - left) / 2;
if(nums[mid] == target){ return mid; }
else if(nums[mid] < target) { left = mid + 1; }
else { right = mid; }
}
// Post-processing:
// End Condition: left == right
if(left != nums.size() && nums[left] == target) return left;
return -1;
}
模板 #2 是二分查找的高级模板。它用于查找需要访问数组中当前索引及其直接右邻居索引的元素或条件。
关键属性
- 一种实现二分查找的高级方法。
- 查找条件需要访问元素的直接右邻居。
- 使用元素的右邻居来确定是否满足条件，并决定是向左还是向右。
- 保证查找空间在每一步中至少有 2 个元素。
- 需要进行后处理。 当你剩下 1 个元素时，循环 / 递归结束。 需要评估剩余元素是否符合条件。
区分语法
- 初始条件：
left = 0, right = length - 终止：
left == right - 向左查找：
right = mid - 向右查找：
left = mid+1
最新文章
- 谈谈一些有趣的CSS题目（六）-- 全兼容的多列均匀布局问题
- Unity3D热更新全书-PageZero
- [ZigBee] 3、ZigBee基础实验——GPIO输出控制实验-控制Led亮灭
- 深入浅出 - Android系统移植与平台开发（八）－ HAL Stub框架分析
- 关于java的static语句块
- MyBatis学习总结_10_批量操作
- 函数buf_page_init_for_read
- C# 数据库dataGridView刷新数据和主外键判断
- 试用阿里云RDS的MySQL压缩存储引擎TokuDB
- Spring 4学习——问题与注意事项（一）
- 性能优化之reflow和repaint
- python3[爬虫实战] 使用selenium，xpath爬取京东手机
- 小游戏canvas直接操作ImgaeData时的几个优化点
- 运行python脚本后台执行
- springmvc 简单框架
- 高并发第二弹:并发概念及内存模型(JMM)
- java===java基础学习（2）---运算符，三元操作符，数学函数
- 可以避免的10大IT面试误区
- mysql--外键（froeign key）-----------MySQL外键使用详解
- Android学习笔记_44_apk安装、反编译及防治反编译