704.二分查找
2023-03-14 22:50:47 时间
递归法:
class Solution {
public:
int search(vector<int>& nums, int target)
{
if (nums.empty()) return -1;
return binarySearch(0, (nums.size() - 1) / 2, nums.size() - 1, nums, target);
}
int binarySearch(int begin, int mid, int end, vector<int>& nums, int target)
{
//结束条件:当前只剩一个元素并且不符合查找值
if (begin>end)
{
return -1;
}
//当前中间值为要查找值
if (nums[mid] == target)
return mid;
if (nums[mid]>target&&binarySearch(begin, (begin + mid - 1) / 2, mid - 1, nums, target)>=0)
{
return binarySearch(begin, (begin + mid - 1) / 2, mid - 1, nums, target);
}
else if(nums[mid]<target&&binarySearch(mid + 1, (mid + end + 1) / 2, end, nums, target)>=0)
{
return binarySearch(mid + 1, (mid + end + 1) / 2, end, nums, target);
}
return -1;
}
};
迭代法:
class Solution {
public:
int search(vector<int>& nums, int target)
{
if (nums.empty()) return -1;
int begin = 0;
int end = nums.size() - 1;
int mid;
while (begin <= end)
{
mid = (begin + end) / 2;
if (nums[mid] > target)
end = mid - 1;
if (nums[mid] < target)
begin = mid + 1;
if (nums[mid] == target)
return mid;
}
return -1;
}
};
相关文章
- Kafka Tools
- 《云数据管理》 2.1 逻辑时间和Lamport时钟
- 应急响应大合集:用于安全事件响应的工具与资源列表
- Docker Machine介绍
- 如何在 Linux 中使用 Asciinema 进行录制和回放终端会话
- 《HttpClient官方文档》2.8 HttpClient代理配置
- Storm ack和fail机制再论
- 通过Ionic构建一个简单的混合式(Hybrid)跨平台移动应用
- 如何安装 pandom : 一个针对 Linux 的真随机数生成器
- storm-kafka-0.8-plus 源码解析
- 《云数据管理》2.1逻辑时间和Lamport时钟
- Samba 系列(九):将 CentOS 7 桌面系统加入到 Samba4 AD 域环境中
- 如何在 Linux 中使用屏幕键盘
- 调查:渗透测试人员最爱的安全工具及技术
- Machine Learning in Action -- Logistic regression
- Linux有问必答:如何修复“ImportError: No module named scapy.all”
- CentOS 上最佳的第三方仓库
- 如何在 Linux 上用 SQL 语句来查询 Apache 日志
- 《HttpClient官方文档》2.6 连接维持存活策略
- Python For Data Analysis -- IPython