二分查找--二分查找算法(朴素二分模板)
2023-12-30 18:58:32
个人主页:Lei宝啊?
愿所有美好如期而遇
本题题目链接https://leetcode.cn/problems/binary-search/description/
算法原理
二段性,我们发现这个数组可以找到某种规律将其分为两段,不断划分下去,最终可以找到target
图示
我们分段初始是可以任意挑选位置的,也可以分成多段,但是分成两段是最优的。
同时,我们上图的箭头代表的是mid,也就是(left+right)除以2,缩小范围也是根据mid指向位置的大小和target对比后得出的。
我们不提数组有序,我们只说二段性,因为后续的二分查找算法数组即使无序,我们依然可以寻找到某种规律去解决。
代码
class Solution {
public:
int search(vector<int>& nums, int target)
{
int lhs = 0;
int rhs = nums.size() - 1;
while(lhs <= rhs)
{
int mid = lhs + (rhs - lhs) / 2;
if(nums[mid] < target)
lhs = mid + 1;
else if(nums[mid] > target)
rhs = mid - 1;
else
return mid;
}
return -1;
}
};
文章来源:https://blog.csdn.net/m0_74824254/article/details/135217067
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!