LeetCode 二分查找模板 III
2024-08-25 23:02:04
模板 #3：
int binarySearch(vector<int>& nums, int target){
if (nums.size() == 0)
return -1;
int left = 0, right = nums.size() - 1;
while (left + 1 < right){
// Prevent (left + right) overflow
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid;
} else {
right = mid;
}
}
// Post-processing:
// End Condition: left + 1 == right
if(nums[left] == target) return left;
if(nums[right] == target) return right;
return -1;
}
模板 #3 是二分查找的另一种独特形式。 它用于搜索需要访问当前索引及其在数组中的直接左右邻居索引的元素或条件。
关键属性
- 实现二分查找的另一种方法。
- 搜索条件需要访问元素的直接左右邻居。
- 使用元素的邻居来确定它是向右还是向左。
- 保证查找空间在每个步骤中至少有 3 个元素。
- 需要进行后处理。 当剩下 2 个元素时，循环 / 递归结束。 需要评估其余元素是否符合条件。
区分语法
- 初始条件：
left = 0, right = length-1 - 终止：
left + 1 == right - 向左查找：
right = mid - 向右查找：
left = mid
最新文章
- Spring profile配置应用
- jQuery get() 函数
- yii2权限控制rbac之菜单menu最详细教程
- MicroSD卡（TF卡）SPI模式实现方法
- python爬虫之採集——360联想词W2版本号
- 关于使用X-UA-Compatible来设置IE浏览器兼容模式
- Head First 设计模式目录
- 关于JAVA实现二维码以及添加二维码LOGO
- Android开发中碰到的一个ANR问题。
- 【spring】-- 手写一个最简单的IOC框架
- CRM系统（第三部分）
- 杨辉三角（java实现）
- Java 详解 JVM 工作原理和流程
- killall 、kill 、pkill 命令详解 【转】
- LG3275 【[SCOI2011]糖果】
- HMM（隐马尔可夫模型）不断学习中
- delphi IsIPAdress 非正则表达式验证IP的方法
- spark踩坑——dataframe写入hbase连接异常
- SourceTree下载 及使用
- 【LeetCode】19. Remove Nth Node From End of List (2 solutions)