二分查找--二分查找算法(朴素二分模板)

2023-12-30 18:58:32

个人主页:Lei宝啊?

愿所有美好如期而遇


本题题目链接icon-default.png?t=N7T8https://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
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。