二分查找模板I
2023-03-14 22:50:49 时间
二分查找模板 I
int binarySearch(vector<int>& nums, int target){
if(nums.size() == 0)
return -1;
int left = 0, right = nums.size() - 1;
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 - 1; }
}
// End Condition: left > right
return -1;
}
区分语法:
- 初始条件:left = 0, right = length-1
- 终止:left > right
- 向左查找:right = mid-1
- 向右查找:left = mid+1
例1:
解法1:
class Solution {
public:
int mySqrt(int x) {
if (x == 0) {
return 0;
}
int ans = exp(0.5 * log(x));
return ((long long)(ans + 1) * (ans + 1) <= x ? ans + 1 : ans);
}
};
解法2:
class Solution {
public:
//到1---x中寻找x的平方根
int mySqrt(int x)
{
int low, high, mid,ans;
low = 0; high = x;
while (low<= high)
{
mid = (low + high) / 2;
if ((long long)mid * mid <= x)
{
ans = mid;
low = mid + 1;
}
else
{
high = mid - 1;
}
}
return ans;
}
};
例2:
解法1:二分查找
class Solution {
public:
int guessNumber(int n) {
int l = 0;
int r = n;
while (l <= r)
{
int m = (l-r)/2 + r;
int res = guess(m);
if (res == 0)
{
return m;
}
else if (res < 0)
{
r = m-1;
}
else
{
l = m + 1;
}
}
return -1;
}
};
例3:
class Solution {
public:
int search(vector<int>& nums, int target)
{
int low = 0;
int high = nums.size() - 1;
while (low <= high)
{
int mid = (low + high) / 2;
if (nums[mid] == target)
return mid;
//先判断mid位于左段还是右端
if (nums[mid] >=nums[low])//mid位于左段
{
//如果此时target同时满足位于左段并且小于nums[mid]的条件,说明target对应下标小于mid
if (target >=nums[low] && target < nums[mid])
high = mid - 1;
else
low = mid + 1;
}
else //mid位于右段
{
if (target > nums[mid] && target <=nums[high])
low = mid + 1;
else
high = mid - 1;
}
}
return -1;
}
};
例三的图解:
相关文章
- 自己动手构造编译系统:编译、汇编与链接1.4 设计自己的编译系统
- 关于移动端布局的几种方式
- 复杂系统研究:从蚁群到互联网
- 自己动手构造编译系统:编译、汇编与链接1.5 本章小结
- 自己动手构造编译系统:编译、汇编与链接2.1 编译程序的设计
- 预测分析:R语言实现1.3 预测建模的过程
- 《科学》最新研究:给“薛定谔猫”第二个盒子会发生什么?
- 自己动手构造编译系统:编译、汇编与链接2.1.1 词法分析
- Activiti实战. 导读
- 自己动手构造编译系统:编译、汇编与链接2.1.2 语法分析
- Activiti实战. 1.1什么是Activiti
- 预测分析:R语言实现1.4 性能衡量指标
- 首席工程师揭秘:LinkedIn大数据后台是如何运作的
- 自己动手构造编译系统:编译、汇编与链接2.1.3 符号表管理
- Activiti实战. 1.2工作流基础
- 自己动手构造编译系统:编译、汇编与链接2.1.4 语义分析
- 自己动手构造编译系统:编译、汇编与链接2.1.5 代码生成
- 自己动手构造编译系统:编译、汇编与链接2.1.6 编译优化
- 自己动手构造编译系统:编译、汇编与链接2.2 x86指令格式
- 自己动手构造编译系统:编译、汇编与链接2.3 ELF文件格式