704.二分查找
查找 二分
2023-09-14 09:02:34 时间
递归法:
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;
}
};
相关文章
- [LeetCode] First Bad Version - 二分查找
- 二分查找
- IDA使用-VS2015版本debug查找Main函数,加载符号文件
- Java实现 LeetCode 704 二分查找(二分法)
- 查找大小为零的文件
- Linux vi中查找字符内容的方法
- (算法)二分查找的搜索区间
- (算法:二分查找)在排序数组中,找出给定数字出现的次数
- 704. 二分查找
- LeetCode-878. 第 N 个神奇数字【数学,二分查找,找规律】
- 如何自行查找出 SAP ABAP 标准的 OData 服务返回数据的后台数据库表和表字段名称试读版
- 【二分查找】查找算法之二分查找(Binary Search)
- 【求根问题】循环查找、二分查找、牛顿迭代法,三种方式求解平方根、立方根问题
- 【华为OD机试 2023】 查找树中元素(C++ Java JavaScript Python)
- 1760. 袋子里最少数目的球-二分查找法
- 【Android 逆向】应用安装目录 ( Android 应用的默认安装目录 | 查找 Android 应用的安装目录 | 查询当前正在运行的应用包名 | 根据包名查询应用安装路径 )
- C++字符串详解(三) 字符串的查找
- 旋转数组的二分查找 代码重构 追求优雅的代码
- 01-复杂度3 二分查找